////#include <stdio.h>
////#include <stdlib.h>
////
////int main()
////{
//// int a, b, i, j, arr[101][101], k=1;
//// scanf("%d %d", &a, &b);
//// for(j=1;j<=b;j++)
//// {
//// if(j%2==1)
//// {
//// for(i=1;i<=a;i++)
//// {
//// arr[i][j]=k++;
//// }
//// }
//// else
//// {
//// for(i=a;i>=1;i--)
//// {
//// arr[i][j]=k++;
//// }
//// }
//// }
//// for(i=a;i>=1;i--)
//// {
//// for(j=b;j>=1;j--)
//// {
//// printf("%d ", arr[i][j]);
//// }
//// printf("\n");
//// }
//// return 0;
////}
///*#include<stdio.h>
//int main()
//{
// int a, b, i, j, arr[101][101], k=1;
// scanf("%d %d", &a, &b);
// for(j=1;j<=b;j++)
// {
// if(j%2==0)
// {
// for(i=1;i<=a;i++)
// {
// arr[i][j]=k++;
// }
// }
// else
// {
// for(i=a;i>=1;i--)
// {
// arr[i][j]=k++;
// }
// }
// }
// for(i=a;i>=1;i--)
// {
// for(j=b;j>=1;j--)
// {
// printf("%d ", arr[i][j]);
// }
// printf("\n");
// }
//}
//#include<stdio.h>
//int main()
//{
// int arr[20][20]={0}, x, y, i, j, a;
// scanf("%d", &a);
// for(i=1; i<=a; i++)
// {
// scanf("%d %d", &x, &y);
// arr[x][y]=1;
// }
// for(i=1; i<=19; i++)
// {
// for(j=1; j<=19; j++)
// {
// printf("%d ", arr[i][j]);
// }
// printf("\n");
// }
//}
//*/
//
//
////#include<stdio.h>
////int main()
////{
//// int a, i, j, arr[20][20];
//// scanf("%d", &a);
//// for(i=1;i<=a;i++)
//// {
//// scanf("%d", &arr[i][1]);
//// }
//// for(i=2;i<=a;i++)
//// {
//// for(j=2;j<=i;j++)
//// {
//// arr[i][j]=arr[i][j-1]-arr[i-1][j-1];
//// }
//// }
//// for(i=1;i<=a;i++)
//// {
//// for(j=1;j<=i;j++)
//// {
//// printf("%d ", arr[i][j]);
//// }
//// printf("\n");
//// }
////}
////#include<stdio.h>
////int main()
////{
//// int arr[12][12], a=0, i, j;
//// for(i=1; i<=11; i++)
//// {
//// for(j=1; j<=10; j++)
//// {
//// scanf("%d", &arr[i][j]);
//// }
//// }
//// for(j=1; j<=10; j++)
//// {
////
////
//// if(arr[11][j]==1)
//// {
//// for(i=10; i>=1; i--)
//// {
//// if(arr[i][j]>0)
//// {
//// printf("%d crash", j);
//// break;
//// }
//// else if(arr[i][j]<0)
//// {
//// printf("%d fall", j);
//// break;
//// }
//// else if(i==1)
//// {
//// printf("%d safe", j);
//// }
////
//// }
//// printf("\n");
//// }
//// }
////}
////
////#include<stdio.h>
////int main()
////{
//// int a, arr[50][50], i, j, k=1,b;
//// scanf("%d", &a);
//// i=1;
//// j=a/2+1;
//// for(b=1;b<=a*a;b++)
//// {
//// arr[i][j]=b;
//// if(b%a==0)
//// {
////
//// if(i==a)
//// {
//// i=1;
//// }
//// else{
//// i+=1;
//// }
//// }
//// else
//// {
//// if(i==1)
//// {
//// i=a;
//// }
//// else
//// {
//// i--;
//// }
////
//// if(j==a)
//// {
//// j=1;
//// }
//// else
//// {
//// j++;
//// }
//// }
////
//// }
//// for(i=1;i<=a;i++)
//// {
//// for(j=1;j<=a;j++)
//// {
//// printf("%d ", arr[i][j]);
//// }
//// printf("\n");
//// }
////}
//#include<stdio.h>
//int main()
//{
// int a, arr[101][101], i, j, sum=0, k=1;
// scanf("%d", &a);
// for(i=1;i<=a;i++)
// {
// for(j=1;j<=a;j++)
// {
// arr[i][j]=k;
// if(i==1||i==a||j==1||j==a)
// {
// sum+=k;
// }
// k++;
// }
// }
// printf("%d", sum);
//}