/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, x, y, a[30][30]= {0},al[30][30]= {0},cnt=0;
for(i = 1; i <= 25; i++)
{
for(j = 1; j <= 25; j++)
{
scanf("%d",&a[i][j]);
}
}
for(i = 1; i <= 25; i++)
{
for(j = 1; j <= 25; j++)
{
cnt = a[i-1][j-1]+a[i-1][j]+a[i-1][j+1]+a[i][j-1]+a[i][j+1]+a[i+1][j-1]+a[i+1][j]+a[i+1][j+1];
if(a[i][j]==0)
{
if(cnt==3)
{
al[i][j]=1;
}
else
{
al[i][j]=0;
}
}
else
{
if(cnt <= 1 || cnt >= 4)
{
al[i][j]=0;
}
else if(cnt == 2 ||cnt == 3)
{
al[i][j]=1;
}
}
}
}
for(i = 1; i <= 25; i++)
{
for(j = 1; j <= 25; j++)
{
printf("%d ",al[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, a, b, c;
int x, y, z, k, cnt = 0;
int arr[172][172] = {0}, arrl[172][172]= {0};
scanf("%d %d",&a,&b);
scanf("%d %d %d",&x,&y,&z);
for(i = 1; i <= a; i++)
{
for(j = 1; j <= b; j++)
{
scanf("%d",&arr[i][j]);
}
}
scanf("%d",&k);
for (c = 1; c <= k; c++)
{
if (c%2==1)
{
for(i = 1; i <= a; i++)
{
for(j = 1; j <= b; j++)
{
cnt = arr[i-1][j-1]+arr[i-1][j]+arr[i-1][j+1]+arr[i][j-1]+arr[i][j+1]+arr[i+1][j-1]+arr[i+1][j]+arr[i+1][j+1];
if(arr[i][j]==0)
{
if(cnt==x)
{
arrl[i][j]=1;
}
else
{
arrl[i][j]=0;
}
}
else
{
if(cnt >= y &&cnt < z)
{
arrl[i][j]=1;
}
else
{
arrl[i][j]=0;
}
}
}
}
}
else
{
for(i = 1; i <= a; i++)
{
for(j = 1; j <= b; j++)
{
cnt = arrl[i-1][j-1]+arrl[i-1][j]+arrl[i-1][j+1]+arrl[i][j-1]+arrl[i][j+1]+arrl[i+1][j-1]+arrl[i+1][j]+arrl[i+1][j+1];
if(arrl[i][j]==0)
{
if(cnt==x)
{
arr[i][j]=1;
}
else
{
arr[i][j]=0;
}
}
else
{
if(cnt >= y &&cnt < z)
{
arr[i][j]=1;
}
else
{
arr[i][j]=0;
}
}
}
}
}
}
if(k%2==1)
{
for(i = 1; i <= a; i++)
{
for(j = 1; j <= b; j++)
{
printf("%d ",arrl[i][j]);
}
printf("\n");
}
}
else
{
for(i = 1; i <= a; i++)
{
for(j = 1; j <= b; j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, a[10][10] = {1},k;
for(i = 0; i <10; i++)
{
for(j = 0; j <10; j++)
{
scanf("%d",&a[i][j]);
}
}
i = 1;
j = 1;
for ( ; ; )
{
if(a[i][j]==0)
{
if(a[i][j+1]==0|| a[i][j+1]==2)
{
a[i][j]=9;
j++;
}
else if(a[i+1][j]==0 || a[i+1][j]==2 )
{
a[i][j]=9;
i++;
}
else if(a[i][j+1]==1 && a[i+1][j]==1)
{
a[i][j]=9;
break;
}
}
else if(a[i][j]==2 || (i == 9 && j == 9))
{
a[i][j]=9;
break;
}
}
for(i = 0; i < 10; i++)
{
for(j = 0; j < 10; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, h, w, n, k, b;
int l, d, x, y, a[100][100] = {0};
scanf("%d %d",&h,&w);
scanf("%d",&n);
for(k = 1; k <= n; k++)
{
scanf("%d %d %d %d",&l,&d,&x,&y);
if(d == 0)
{
for(b = 0; b < l; b++)
{
a[x][y] = 1;
y++;
}
}
else
{
for(b = 0; b < l; b++)
{
a[x][y] = 1;
x++;
}
}
}
for(i = 1; i <= h; i++)
{
for(j = 1; j <= w; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}
*/