/*#include <stdio.h>
int main () {
int n,d,m,k=1,i,j,arr[100][100]={};
scanf("%d %d",&n,&m);
for(j=m-1;j>=0;j--){
if(j%2==(m-1)%2){
for(i=n-1;i>=0;i--){
arr[i][j]=k;
k++;
}
}
else{
for(i=0;i<n;i++){
arr[i][j]=k;
k++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main () {
int i,j,k=1,t,n,arr[20][20]={};
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&arr[i][0]);
}
for(i=1;i<n;i++){
for(j=1;j<i+1;j++){
arr[i][j]=arr[i][j-1]-arr[i-1][j-1];
}
}
for(i=0;i<n;i++){
for(j=0;j<i+1;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main ()
{
int i,j,k=0,t,arr[11][10]= {};
for(i=0; i<11; i++)
{
for(j=0; j<10; j++)
{
scanf("%d",&arr[i][j]);
}
}
for(j=0; j<10; j++){
if(arr[10][j]==0)
{
continue;
}
else
{
for(i=9; i>=0; i--)
{
if(arr[i][j]<0)
{
printf("%d fall\n",j+1);
break;
}
else if(arr[i][j]>0){
printf("%d crash\n",j+1);
break;
}
if(i==0){
printf("%d safe\n",j+1);
}
}
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main () {
int i,j,a,b,k=0,t,arr[11][11]={};
for(i=1;i<=9;i++){
for(j=1;j<=9;j++){
scanf("%d",&arr[i][j]);
}
}
scanf("%d %d",&a,&b);
if(arr[a][b]==1){
printf("-1");
}
else{
for(i=a-1;i<=a+1;i++){
for(j=b-1;j<=b+1;j++){
if(arr[i][j]==1&&(i!=a||j!=b)){
k++;
}
}
}
printf("%d",k);
}
}
*/
/*
#include <stdio.h>
int main ()
{
int i, j, t, k=0, a, b, arr[28][28]= {}, lst[28][28]= {};
for(i=1; i<=25; i++)
{
for(j=1; j<=25; j++)
{
scanf("%d",&arr[i][j]);
lst[i][j]=arr[i][j];
}
}
for(i=1; i<=25; i++)
{
for(j=1; j<=25; j++)
{
for(a=i-1; a<=i+1; a++)
{
for(b=j-1; b<=j+1; b++)
{
if(arr[a][b]==1&&(a!=i||b!=j))
{
k++;
}
}
}
if(arr[i][j]==0&&k==3)
{
lst[i][j]=1;
}
else if(arr[i][j]==1&&(k<=1||k>=4)){
lst[i][j]=0;
}
k=0;
}
}
for(i=1;i<=25;i++){
for(j=1;j<=25;j++){
printf("%d ",lst[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main () {
int i, j, t, k, n, m, len, x, y, z, arr[105][105]={};
scanf("%d %d %d",&n,&m,&t);
for(i=1;i<=t;i++){
scanf("%d %d %d %d",&len,&k,&x,&y);
if(k==0){
for(z=0;z<len;z++){
arr[x][y+z]=1;
}
}
else{
for(z=0;z<len;z++){
arr[x+z][y]=1;
}
}
}
for(i=1;i<n+1;i++){
for(j=1;j<m+1;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main () {
int i, j, t=0, k, x=2 ,y=2 , arr[14][14]={};
for(i=1;i<=10;i++){
for(j=1;j<=10;j++){
scanf("%d",&arr[i][j]);
}
}
while(1){
if(arr[x][y]==2){
arr[x][y]=9;
break;
}
arr[x][y]=9;
if(arr[x][y+1]==0 || arr[x][y+1]==2){
y++;
}
else if(arr[x+1][y]==1){
break;
}
else{
x++;
}
}
for(i=1;i<=10;i++){
for(j=1;j<=10;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}*/
/*
#include <stdio.h>
int main () {
int i, j, t=0, k=1, n, arr[51][51]= {};
scanf("%d",&n);
i=1;
j=1;
while(k<=n*n){
arr[i][j]=k;
k++;
if(t==0){
if(arr[i][j+1]!=0||j==n){
t++;
i++;
}
else{
j++;
}
}
else if(t==1){
if(arr[i+1][j]!=0||i==n){
t++;
j--;
}
else{
i++;
}
}
else if(t==2){
if(arr[i][j-1]!=0||j==1){
t++;
i--;
}
else{
j--;
}
}
else{
if(arr[i-1][j]!=0){
t=0;
j++;
}
else{
i--;
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main () {
int n,x1 ,y1 ,x2 ,y2 , i, j, t=0, k, arr[103][103]= {};
for(n=1;n<=4;n++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(i=x1;i<x2;i++){
for(j=y1;j<y2;j++){
arr[i][j]=1;
}
}
}
for(i=1;i<=100;i++){
for(j=1;j<=100;j++){
if(arr[i][j]==1){
t++;
}
}
}
printf("%d",t);
}
*/
/*
#include <stdio.h>
int main ()
{
int n, i, j,k=1, arr[53][53];
scanf("%d",&n);
i=1;
j=n/2+1;
while(k<=n*n)
{
arr[i][j]=k;
k++;
if((k-1)%n==0)
{
if(i==n){
i=1;
}
else{
i++;
}
}
else
{
if(i-1==0)
{
i=n;
}
else
{
i--;
}
if(j==n)
{
j=1;
}
else
{
j++;
}
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
}
*/
/*
#include <stdio.h>
int main () {
int n, i , j, t, k=0, arr[100][100];
scanf("%d",n);
while(k==)
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%d",arr[i][j]);
}
}
}
*/