/*
#include <stdio.h>
int main()
{
int a[20][20]={};
int n, i, j;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i][0]);
}
for(j=0; j<n; j++)
for(i=0; i<n; i++)
{
for(j=1; j<=i; j++)
{
a[i][j]=a[i][j-1]-a[i-1][j-1];
}
}
for(i=0; i<n; i++)
{
for(j=0; j<=i; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int i, j, m, n, k, t=1, a=1;
int arr[99][99]={};
scanf("%d", &k);
n=k-1;
m=0;
while(1){
arr[n][m]=t;
if(n==k-1 && m==k-1) break;
t++;
if(a==1)
{
if(n>0)
{
if(m+1<k)
{
n--;
m++;
}
else
{
n++;
a = 2;
}
}
else
{
n++;
a=2;
}
}
else if(a==2)
{
if(n+1<k)
{
if(m>0)
{
n++;
m--;
}
else
{
m=k-1;
a=1;
}
}
else
{
a=1;
m++;
}
}
}
for(i=0; i<k; i++)
{
for(j=0; j<k; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, a[12][11], sum=0;
for(i=1; i<=11; i++)
{
for(j=1; j<=10; j++)
{
scanf("%d", &a[i][j]);
}
}
for(i=1; i<=10; i++)
{
if(a[11][i]==1)
{
sum=0;
for(j=10; j>=1; j--)
{
if(a[j][i]==0)
{
sum++;
if(sum==10)
{
printf("%d safe\n", i);
}
}
else if(a[j][i]>0)
{
printf("%d crash\n", i);
break;
}
else if(a[j][i]<0)
{
printf("%d fall\n", i);
break;
}
}
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int h, w, n, l, d, x, y, i, j, k, z;
int a[100][100]={};
scanf("%d %d", &w, &h);
for(j=1;j<=w;j++)
{
for(i=1;i<=h;i++)
{
a[i][j]=0;
}
}
scanf("%d", &n);
for(k=1;k<=n;k++)
{
scanf("%d %d %d %d", &l, &d, &x, &y);
if(d==1)
{
for(z=1;z<=l;z++)
{
a[y][x]=1;
x=x+1;
}
}
else
{
for(z=1;z<=l;z++)
{
a[y][x]=1;
y=y+1;
}
}
}
for(j=1;j<=w;j++)
{
for(i=1;i<=h;i++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int n, m;
scanf("%d %d", &n, &m);
int a[100][100]={};
int k=1;
for(int i=0; i<m; i++)
{
if(i%2==0)
{
for(int j=n-1; j>=0; j--)
{
a[j][i]=k; k++;
}
}
else
{
for(int j=0; j<=n-1; j++)
{
a[j][i]=k; k++;
}
}
}
for(int i=0; i<n; i++)
{
for(int j=m-1; j>=0; j--)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
}
*/