/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a[50][50],n,i,j,k=1,x,y;
scanf("%d",&n);
x=0;
y=n/2;
for(i=0; i<n*n; i++)
{
a[x][y]=k;
if(k%n==0)
{
x++;
}
else
{
if(x==0)
{
x=n-1;
}
else
{
x--;
}
if(y==n-1)
{
y=0;
}
else
{
y++;
}
}
k++;
}
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a[11][10],n,i,j,k=1;
for(i=0;i<11;i++){
for(j=0;j<10;j++){
scanf("%d",&a[i][j]);
}
}
for(j=0;j<10;j++){
if(a[10][j]==1)
{
for(i=9;i>=0;i--)
{
if(a[i][j]>0){
printf("%d crash\n",j+1);
break;
}
else if(a[i][j]<0){
printf("%d fall\n",j+1);
break;
}
else if(i==0){
printf("%d safe\n",j+1);
}
}
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a[100][100]={0},h,w,n,l,d,x,y,i,j;
scanf("%d %d %d",&h,&w,&n);
for(i=0;i<n;i++){
scanf("%d %d %d %d",&l,&d,&x,&y);
for(j=0;j<l;j++){
if(d==0){
a[x][y+j]=1;
}
else{
a[x+j][y]=1;
}
}
}
for(i=1;i<=h;i++){
for(j=1;j<=w;j++){
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a[11][11],n,x,y,i,j;
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)
{
a[i][j]=9;
if(a[i][j+1]==0)
{
j++;
}
else if (a[i][j+1]==1)
{
if(a[i+1][j]==0)
{
i++;
}
else if(a[i+1][j]==1)
{
break;
}
else if (a[i+1][j]==2)
{
a[i+1][j]=9;
break;
}
}
else
{
a[i][j+1]=9;
break;
}
}
else if(a[i][j]==2)
{
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;
}
*/