/*#include <stdio.h>
int home[313]={};
int danji=0,n;
int a[26][26]={};
int bfs(int x,int y){
if(a[x][y]==0||x==-1||y==-1)return 0;
a[x][y]=0;
return bfs(x,y+1)+bfs(x,y-1)+bfs(x-1,y)+bfs(x+1,y)+1;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%1d",&a[i][j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]){
home[danji]=bfs(i,j);
danji++;
}
}
}
printf("%d\n",danji);
for(int i=0;i<danji;i++){
int m=home[0];
int mi=0;
for(int j=1;j<danji;j++){
if(home[j]<m){
m=home[j];
mi=j;
}
}
printf("%d\n",m);
home[mi]=999;
}
return 0;
}*/
//단지 번호 붙이기
/*#include<stdio.h>
int graph[101][101]={};
int q[100]={1};
int head=1,tail=0;
int n,m,x,y;
void virus(){
if(head==tail)return;
int t=q[tail];
for(int i=1;i<=n;i++){
if(graph[t][i]){
int p=1;
for(int j=tail;j<head;j++){
if(q[j]==i){
p=0;
break;
}
}
if(p){
q[head]=i;
head++;
}
graph[t][i]=0;
graph[i][t]=0;
}
}
q[tail]=0;
tail++;
virus();
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
graph[x][y]=1;
graph[y][x]=1;
}
virus();
printf("%d",head-1);
return 0;
}*/
//바이러스
/*#include<stdio.h>
int a[1001][1001]={};
int qx[1000000]={};
int qy[1000000]={};
int n,m,day=0,head=0,tail=0,z=0;
int main(){
scanf("%d%d",&m,&n);
for(int i=0;i<n;i++){
a[i][m]=-1;
for(int j=0;j<m;j++){
scanf("%d",&a[i][j]);
if(a[i][j]==1){
qx[head]=i;
qy[head]=j;
head++;
z++;
}else if(a[i][j]==0){
z++;
}
}
}
for(int i=0;i<=m;i++){
a[n][i]=-1;
}
while(head-tail){
int x=qx[tail];
int y=qy[tail];
if(a[x+1][y]==0){
day=a[x][y];
a[x+1][y]=day+1;
qx[head]=x+1;
qy[head]=y;
head++;
}
if(a[x-1][y]==0&&x){
day=a[x][y];
a[x-1][y]=day+1;
qx[head]=x-1;
qy[head]=y;
head++;
}
if(a[x][y+1]==0){
day=a[x][y];
a[x][y+1]=day+1;
qx[head]=x;
qy[head]=y+1;
head++;
}
if(a[x][y-1]==0&&y){
day=a[x][y];
a[x][y-1]=day+1;
qx[head]=x;
qy[head]=y-1;
head++;
}
qx[tail]=0;
qy[tail]=0;
tail++;
z--;
}
if(z){
printf("-1");
}else{
printf("%d",day);
}
}*/
//토마토(고등)
/*#include<stdio.h>
int a[100][100][100]= {};
int qx[1000000]= {};
int qy[1000000]= {};
int qz[1000000]= {};
int m,n,h,day=0,o,head=0,tail=0;
int main()
{
scanf("%d%d%d",&m,&n,&h);
o=m*n*h;
for(int i=0; i<h; i++)
{
for(int j=0; j<n; j++)
{
for(int k=0; k<m; k++)
{
scanf("%d",&a[j][k][i]);
if(a[j][k][i]==1)
{
qx[head]=j;
qy[head]=k;
qz[head]=i;
head++;
}
else if(a[j][k][i]==-1)
o--;
}
}
}
while(head-tail)
{
int x=qx[tail];
int y=qy[tail];
int z=qz[tail];
if(x-n+1&&a[x+1][y][z]==0)
{
day=a[x][y][z];
a[x+1][y][z]=day+1;
qx[head]=x+1;
qy[head]=y;
qz[head]=z;
head++;
}
if(x&&a[x-1][y][z]==0)
{
day=a[x][y][z];
a[x-1][y][z]=day+1;
qx[head]=x-1;
qy[head]=y;
qz[head]=z;
head++;
}
if(y-m+1&&a[x][y+1][z]==0)
{
day=a[x][y][z];
a[x][y+1][z]=day+1;
qx[head]=x;
qy[head]=y+1;
qz[head]=z;
head++;
}
if(y&&a[x][y-1][z]==0)
{
day=a[x][y][z];
a[x][y-1][z]=day+1;
qx[head]=x;
qy[head]=y-1;
qz[head]=z;
head++;
}
if(z-h+1&&a[x][y][z+1]==0)
{
day=a[x][y][z];
a[x][y][z+1]=day+1;
qx[head]=x;
qy[head]=y;
qz[head]=z+1;
head++;
}
if(z&&a[x][y][z-1]==0)
{
day=a[x][y][z];
a[x][y][z-1]=day+1;
qx[head]=x;
qy[head]=y;
qz[head]=z-1;
head++;
}
qx[tail]=0;
qy[tail]=0;
qz[tail]=0;
tail++;
o--;
}
if(o)
{
printf("-1");
}
else
{
printf("%d",day);
}
return 0;
}*/
//토마토(초등)
/*#include<stdio.h>
int a[11][11]={},b[10][10]={},r,c;//b:공개되면 1, 아니면 0
void ifb(int x,int y){
if(x==0||y==0||x==10||y==10||b[x][y])return;
if(a[x][y]==9){
return;
}else if(a[x][y]==0){
b[x][y]=1;
ifb(x+1,y+1);
ifb(x+1,y-1);
ifb(x+1,y);
ifb(x-1,y+1);
ifb(x-1,y-1);
ifb(x-1,y);
ifb(x,y+1);
ifb(x,y-1);
}else{
b[x][y]=1;
}
}
int main(){
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
scanf("%d",&a[i][j]);
a[i][j]*=9;
}
}
scanf("%d%d",&r,&c);
if(a[r][c]==9){
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
if(i==r&&j==c){
printf("-1 ");
}else{
printf("_ ");
}
}
printf("\n");
}
return 0;
}
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
if(a[i][j]-9){
if(a[i+1][j+1]==9)a[i][j]++;
if(a[i+1][j-1]==9)a[i][j]++;
if(a[i+1][j]==9)a[i][j]++;
if(a[i-1][j+1]==9)a[i][j]++;
if(a[i-1][j-1]==9)a[i][j]++;
if(a[i-1][j]==9)a[i][j]++;
if(a[i][j+1]==9)a[i][j]++;
if(a[i][j-1]==9)a[i][j]++;
}
}
}
ifb(r,c);
for(int i=1;i<10;i++){
for(int j=1;j<10;j++){
if(b[i][j]){
printf("%d ",a[i][j]);
}else{
printf("_ ");
}
}
printf("\n");
}
}*/
//지뢰찾기 2
/*#include<stdio.h>
int p[201]={0,1};
int P(n){
if(p[n])return p[n];
if(n==0)return 0;
p[n]=(P(n-1)+P(n-2))%10009;
return P(n);
}
int main(){
int n;
scanf("%d",&n);
printf("%d",P(n));
return 0;
}*/
//피보나치수열
/*#include<stdio.h>
int block(int n){
if(n==0)return 1;
if(n%3)return 0;
return (2*block(n-3))%100000007;
}
int main(){
int n;
scanf("%d",&n);
printf("%d",block(n));
}*/
//블럭 채우기 2
/*#include<stdio.h>
int p[10001]={1,1};
int b(int n){
if(p[n])return p[n];
p[n]=(b(n-1)+2*b(n-2))%100007;
return p[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",b(n));
}*/
//블럭 채우기 3
/*#include<stdio.h>
int p[10001]={1,1,5};
int b(int n){
if(p[n])return p[n];
p[n]=(b(n-1)+4*b(n-2)+2*b(n-3))%100007;
return p[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",b(n));
return 0;
}*/
//블럭 채우기 4
/*#include<stdio.h>
int p[10001]={0,1,2,6};
int b(int n){
if(p[n])return p[n];
p[n]=(b(n-1)+b(n-2)+3*b(n-3))%1000;
return p[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",b(n));
return 0;
}*/
//블럭 채우기 5
/*#include<stdio.h>
int p[10001]={1,2,7};
int b(int n){
if(p[n])return p[n];
p[n]=(3*b(n-1)+b(n-2)-b(n-3))%100007;
if(p[n]<0)p[n]+=100007;
return p[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",b(n));
return 0;
}*/
//블럭 채우기 6
/*#include<stdio.h>
int p[10001]={1,0,3};
int b(int n){
if(n%2)return 0;
if(p[n])return p[n];
p[n]=(4*b(n-2)-b(n-4))%100007;
if(p[n]<0)p[n]+=100007;
return p[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",b(n));
return 0;
}*/
//블럭 채우기 7
/*#include<stdio.h>
int p[10001]={0,1,5,11,36};
int b(int n){
if(n%2)return 0;
if(p[n])return p[n];
p[n]=(4*b(n-2)-b(n-4))%100007;
if(p[n]<0)p[n]+=100007;
return p[n];
}
int main(){
int n;
scanf("%d",&n);
printf("%d",b(n));
return 0;
}*/
//블럭 채우기 8 점화식 못찾음