/*
#include <stdio.h>
int main()
{
int a[10][10]={};
int i, j;
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
{
scanf("%d", &a[i][j]);
}
}
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
{
if(a[i][j]>0)
{
for(int k=1; k<=a[i][j]; k++)
{
if(j+k>=10 || a[i][j+k]==-1)
{
break;
}
if(a[i][j+k]==0)
{
a[i][j+k]=-2;
}
}
for(int k=1; k<=a[i][j]; k++)
{
if(i+k>=10 || a[i+k][j]==-1)
{
break;
}
if(a[i+k][j]==0)
{
a[i+k][j]=-2;
}
}
for(int k=1; k<=a[i][j]; k++)
{
if(i-k<0 || a[i-k][j]==-1)
{
break;
}
if(a[i-k][j]==0)
{
a[i-k][j]=-2;
}
}
for(int k=1; k<=a[i][j]; k++)
{
if(j-k<0 || a[i][j-k]==-1)
{
break;
}
if(a[i][j-k]==0)
{
a[i][j-k]=-2;
}
}
a[i][j]=-2;
}
}
}
int n;
int m[8][2]={};
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d %d", &m[i][0], &m[i][1]);
if(a[m[i][0]-1][m[i][1]-1]!=-2)
{
a[m[i][0]-1][m[i][1]-1]=i+1;
}
}
for(i=0; i<10; i++)
{
for(j=0; j<10; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
printf("Character Information\n");
for(i=0; i<n; i++)
{
if(a[m[i][0]-1][m[i][1]-1]==-2)
{
printf("player %d dead\n", i+1);
}
else
{
printf("player %d survive\n", i+1);
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int arr_now[25][25];
int arr_nxt[25][25];
int tsum;
for(int i=0; i<25; i++)
{
for(int j=0; j<25; j++)
{
scanf("%d", &arr_now[i][j]);
arr_nxt[i][j] = arr_now[i][j];
}
}
for(int i=0; i<25; i++)
{
for(int j=0; j<25; j++)
{
tsum=0;
for(int ser=i-1; ser<=i+1; ser++)
{
for(int gar=j-1; gar<=j+1; gar++)
{
if(ser!=-1&&ser!=25&&gar!=-1&&gar!=25)
{
if(ser!=i || gar!=j)
{
tsum+=arr_now[ser][gar];
}
}
}
}
if(arr_now[i][j]==0 && tsum==3)
{
arr_nxt[i][j]=1;
}
if(arr_now[i][j]==1 && (tsum>=4 || tsum<=1))
{
arr_nxt[i][j]=0;
}
if(arr_now[i][j]==1 && (tsum==2 || tsum==3))
{
arr_nxt[i][j]=1;
}
}
}
for(int i=0; i<25; i++)
{
for(int j=0; j<25; j++)
{
printf("%d ", arr_nxt[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n;
int a, b;
scanf("%d", &n);
int arr[100][100]={};
int cnt=0;
for (int i=1; i<=n; i++)
{
scanf("%d %d", &a, &b);
for (int j = a; j < a + 10; j++)
{
for (int k=b; k<b+10; k++)
{
if (arr[j][k]==0)
{
arr[j][k]=1;
cnt++;
}
}
}
}
printf("%d\n", cnt);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a[101][101]={};
int x1, y1, x2, y2;
for(int i=0; i<4; i++)
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
for(int j=x1; j<x2; j++)
{
for(int k=y1; k<y2; k++)
{
a[j][k]=1;
}
}
}
int result=0;
for(int i=0; i<101; i++)
{
for(int j=0; j<101; j++)
{
if(a[i][j]==1)
{
result++;
}
}
}
printf("%d", result);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
{
for(int j=0; j<i+1; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
for(int i=n; i>0; i--)
{
for(int j=0; j<i; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
int main()
{
int a, i, j;
int k;
scanf("%d", &a);
for (i = 1; i <= a; i++)
{
for (k = 1; k <= i-1; k++)
{
printf(" ");
}
for (j = i; j <= a; j++)
{
printf("*");
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=((n+1)/2);i++)
{
for (j=1;j<=n;j++)
{
if (j<=((n-1)/2+1-i)||j>=((n-1)/2+i+1))
printf(" ");
else
printf("*");
}
if(i<((n+1)/2))
{
printf("\n"); j=0;
}
}
}
*/