/*
#include <stdio.h>
#include <stdlib.h>
//1099
int main()
{
}
#include <stdio.h>
int main()
{
int a[10][10]={0}, b[10][10]={-5}, i, j, c, p[10]={0}, k, u=1,d=1,l=1,r=1 ;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
scanf("%d", &a[i][j]);
}
}
for(k=0;k<10;k++)
{
for(i=0;i<10;i++)
{
if(a[k][i]>=1)
{
b[k][i]=-2;
for(j=0;j<=a[k][i];j++)
{
if(k+j<10)
{
if(a[k+j][i]!=-1&&d==1)
b[k+j][i]=-2;
else
d=0;
}
if(i+j<10)
{
if(a[k][i+j]!=-1&&l==1)
b[k][i+j]=-2;
else
l=0;
}
if(k-j>=0)
{
if(a[k-j][i]!=-1&&u==1)
b[k-j][i]=-2;
else
u=0;
}
if(i-j>=0)
{
if(a[k][i-j]!=-1&&r==1)
b[k][i-j]=-2;
else
r=0;
}
}
}
if(b[k][i]!=-2)
b[k][i]=a[k][i];
l=1;
r=1;
u=1;
d=1;
}
}
scanf("%d", &c);
for(i=0;i<c;i++)
{
scanf("%d %d", &j, &k);
if(b[j-1][k-1]==-2)
p[i]=0;
else
{
b[j-1][k-1]=i+1;
p[i]=1;
}
}
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d ", b[i][j]);
}
printf("\n");
}
printf("Character Information\n");
for(i=0;i<c;i++)
{
if(p[i]!=1)
printf("player %d dead\n", i+1);
else
printf("player %d survive\n", i+1);
}
return 0;
}
*/
//1285
/*
#include <stdio.h>
int main()
{
char a;
int A, B, sum=0, i;
scanf("%d", &sum);
for(;;)
{
scanf("%c", &a);
if(a=='=')
break;
scanf("%d", &B);
if(a=='*')
sum*=B;
else if(a=='/')
sum/=B;
else if(a=='+')
sum+=B;
else if(a=='-')
sum-=B;
printf(">>sum : %d\n",sum);
}
printf("%d", sum);
}*/
//1284
/*
#include <stdio.h>
int main()
{
int a, b, c, i, j;
scanf("%d", &a);
for(i=2;i<a;i++)
{
if(a%i==0)
{
for(j=2;j<i;j++)
{
if(i%j==0)
break;
else
}
}
}
}
*/
//1167
/*
#include <stdio.h>
int main()
{
int a[3]={0},b,c,i,j,t;
for(i=0;i<3;i++)
{
scanf("%d", &a[i]);
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
printf("%d", a[1]);
}*/
//1172
/*
#include <stdio.h>
int main()
{
int a[3]={0},b,c,i,j,t;
for(i=0;i<3;i++)
{
scanf("%d", &a[i]);
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=0;i<3;i++)
{
printf("%d ", a[i]);
}
return 0;
}*/
//1505
/*
#include <stdio.h>
int main()
{
int a[51][51]= {0}, i, j, k, n, m, p;
scanf("%d", &n);
m=n;
i=1; j=n;
for(k=1;k<=n;k++) a[1][k]=k;
//while(k<=n*n)
for(k=n+1;k<=n*n;)
{
m--;
for(p=1;p<=m;p++) a[++i][j]=k++;
for(p=1;p<=m;p++) a[i][--j]=k++;
m--;
for(p=1;p<=m;p++)
{
i--;
a[i][j]=k++;
}
for(p=1;p<=m;p++)
{
j++;
a[i][j]=k++;
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
else
{
if(dir==0)
{
a[1+c][i-3*n]=i;
if(i-3*n==n-c)
dir=1;
continue;
}
else if(dir==1)
{
a[i+1-n][n-c]=i;
if(i==2*n-1)
dir=2;
continue;
}
else if(dir==2)
{
a[n][3*n-1-i]=i;
if(i==3*n-2)
dir=3;
continue;
}
else if(dir==3)
{
a[4*n-2-i][1]=i;
if(i==4*n-4)
c=1;
continue;
}
}
*/
/*
#include <stdio.h>
int main()
{
int n, a[51][51]= {0}, i, j, dir=0, c=0,m;
scanf("%d", &n);
m=n;
for(i=1; i<=m*m; i++)
{
if(dir==0)
{
a[1][i]=i;
if(i==n) dir=1;
}
else if(dir==1)
{
a[i+1-n][n]=i;
if(i==2*n-1) dir=2;
}
else if(dir==2)
{
a[n][3*n-1-i]=i;
if(i==3*n-2)
dir=3;
}
else if(dir==3)
{
a[4*n-2-i][1]=i;
if(i==4*n-4)
{
dir=0;
//n-=2;
}
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
printf("%2d ", a[i][j]);
}
printf("\n");
}
return 0;
}
*/
//1485
/*
#include <stdio.h>
int main()
{
int a[101][101]= {0}, i, j, k, p, x, y, x1, y1;
scanf("%d %d", &x, &y);
x1=x;
y1=y;
i=1; j=y;
k=x*y;
for(p=1;p<=y;p++)
{
a[1][k]=k;
k--;
}
//while(k<=n*n)
for(k=x*y-y-1;k>=1;)
{
x1--;
y1--;
for(p=1;p<=x1&&k<=x*y;p++) a[++i][j]=k--;
for(p=1;p<=y1&&k<=x*y;p++) a[i][--j]=k--;
x1--;
y1--;
for(p=1;p<=x1&&k<=x*y;p++) a[--i][j]=k--;
for(p=1;p<=y1&&k<=x*y;p++) a[i][++j]=k--;
}
for(i=1; i<=x; i++)
{
for(j=1; j<=y; j++) printf("%d ", a[i][j]);
printf("\n");
}
return 0;
}
*/
//1099
/*
#include<stdio.h>
int main()
{
int i, j,a[10][10]={0}, b[10][10]={0}, x, y, c=0;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
scanf("%d", &a[i][j]);
b[i][j]=a[i][j];
}
}
b[1][1]=9;
x=1; y=1;
for(i=1;i<9;i++)
{
if(a[x][i]==2)
{
b[x][i]=9;
break;
}
else if(a[x][i+1]==1&&c==0)
{
for(j=x;j<9;j++)
{
b[j][i]=9;
if(a[j][i]==2)
{
b[x][i]=9;
c=1;
break;
}
else if(a[j][i+1]!=1)
{
x=j;
break;
}
}
}
else if(c==0)
{
b[x][i]=9;
}
}
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
#include<stdio.h>
int main()
{
int i, j,a[10][10]={0}, x, y, c=0;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
scanf("%d", &a[i][j]);
}
}
x=1; y=1;
for(;;)
{
if(a[x][y]==2)
{
a[x][y]=9;
break;
}
else if(a[x][y]==0) a[x][y]=9;
if(a[x][y+1]!=1) y++;
else if(a[x+1][y]!=1) x++;
else break;
}
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
*/
//1510
/*
#include <stdio.h>
int main()
{
int a[50][50]={},n, x,y,i;
scanf("%d", &n);
x=1,y=n/2+1;
a[x][y]=1;
for(i=2;i<=n*n;i++)
{
if(i%n-1!=0)
{
if(x-1==0) x=n;
else x--;
if(y==n) y=1;
else y++;
a[x][y]=i;
}
else
{
if(x==n) x=1;
else x++;
a[x][y]=i;
}
}
for(x=1;x<=n;x++)
{
for(y=1;y<=n;y++)printf("%d ", a[x][y]);
printf("\n");
}
}*/
//1512
/*
#include<stdio.h>
int main()
{
int n,x,y,i,j;
int a[102][102]={0};
scanf("%d", &n);
scanf("%d %d", &x, &y);
a[x][y]=1;
for(i=1;i<=n;i++)
{
if(x-i>0) a[x-i][y]=i+1;
if(x+i<=n) a[x+i][y]=i+1;
if(y-i>0) a[x][y-i]=i+1;
if(y+i<=n) a[x][y+i]=i+1;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(x-i!=0) a[x-i][j]=a[x-i+1][j]+1;
if(x+i<=n) a[x+i][j]=a[x+i-1][j]+1;
}
}
for(x=0;x<=n+1;x++)
{
for(y=0;y<=n+1;y++)printf("%d ", a[x][y]);
printf("\n");
}
return 0;
}
*/
//1513
/*
#include<stdio.h>
int main()
{
int a[101][101]={0},n,i,j,x,y,x1=0,y1=1, m=0;
scanf("%d", &n);
x=n;y=1;
a[x][y]=1;
for(i=2;i<=n*n;i++)
{
if(y>=n)
{
x1=1;
y1=0;
++x;
if(x==n&&y==n)
{
a[x][y]=i;
break;
}
a[x][y]=i;
i++;
}
if(x>=n&&i!=2)
{
x1=0;
y1=1;
++y;
if(x==n&&y==n)
{
a[x][y]=i;
break;
}
a[x][y]=i;
i++;
}
if(x1) ++x;
else --x;
if(y1) ++y;
else --y;
a[x][y]=i;
}
for(x=1;x<=n;x++)
{
for(y=1;y<=n;y++)printf("%d ", a[x][y]);
printf("\n");
}
}
*/