//#include <stdio.h>
//
//int main()
//{
// printf("Hello world!\n");
// return 0;
//}
//#include <stdio.h>
//
//int main()
//{
// int a[49][49], i, j, n, d;
// scanf("%d", &n);
// i=0;
// j=(n-1)/2;
// for(d=1;d<=n*n;d++)
// {
// a[i][j]=d;
// if(a[i][j]%n==0)
// {
// i++;
// }
// else
// {
// if(i==0)
// {
// i=n-1;
// }
// else
// {
// i--;
// }
// if(j==n-1)
// {
// j=0;
// }
// else
// {
// j++;
// }
// }
// }
// 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[20][20]={0}, i, j, n, d;
// scanf("%d", &n);
// for(i=0;i<n;i++)
// {
// scanf("%d", &a[i][0]);
// }
// for(i=1;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 a[100][100]={0}, i, j, d, b, m, n=0, w, e;
// for(m=0;m<4;m++)
// {
// scanf("%d %d %d %d", &d, &b, &w, &e);
// for(i=d;i<w;i++)
// {
// for(j=b;j<e;j++)
// {
// a[i][j]=1;
// }
// }
// }
// for(i=0;i<100;i++)
// {
// for(j=0;j<100;j++)
// {
// n+=a[i][j];
// //printf("%d ",a[i][j]);
// }
// // printf("\n");
// }
// printf("%d", n);
// return 0;
//
//}
//#include <stdio.h>
//
//int main()
//{
// int a[100][100]={0}, i, j, h, w, n, l, d, x, y, b;
// scanf("%d %d %d", &w, &h, &n);
// for(b=0;b<n;b++)
// {
// scanf("%d %d %d %d", &l, &d, &x, &y);
// if(d==0)
// {
// a[x-1][y-1]=1;
// for(i=1;i<=l-1;i++)
// {
// a[x-1][y-1+i]=1;
// }
// }
// if(d==1)
// {
// a[x-1][y-1]=1;
// for(i=1;i<=l-1;i++)
// {
// a[x-1+i][y-1]=1;
// }
// }
//
//
// }
// for(i=0;i<w;i++)
// {
// for(j=0;j<h;j++)
// {
// printf("%d ", a[i][j]);
// }
// printf("\n");
// }
// return 0;
//}
//#include <stdio.h>
//
//int main()
//{
// int a[11][11]={0}, i, j, r, c, d=0;
// for(i=1;i<=9;i++)
// {
// for(j=1;j<=9;j++)
// {
// scanf("%d", &a[i][j]);
// }
// }
// scanf("%d %d", &r, &c);
// if(a[r][c]==1)
// {
// printf("%d", -1);
// }
// else
// {
// d=a[r+1][c]+a[r+1][c+1]+a[r][c+1]+a[r+1][c-1]+a[r-1][c-1]+a[r][c-1]+a[r-1][c]+a[r-1][c+1];
// printf("%d", d);
// return 0;
// }
//}
//#include <stdio.h>
//
//int main()
//{
// int a[19][19], i, j, n, x, y, d;
// for(i=0;i<19;i++)
// {
// for(j=0;j<19;j++)
// {
// scanf("%d", &a[i][j]);
// }
// }
// scanf("%d", &n);
// for(d=0;d<n;d++)
// {
// scanf("%d %d", &x, &y);
// x--;
// y--;
// for(i=0;i<19;i++)
// {
// if(a[x][i]==1)
// {
// a[x][i]=0;
// }
// else
// {
// a[x][i]=1;
// }
// }
// for(j=0;j<19;j++)
// {
// if(a[j][y]==1)
// {
// a[j][y]=0;
// }
// else
// {
// a[j][y]=1;
// }
// }
// }
// for(i=0;i<19;i++)
// {
// for(j=0;j<19;j++)
// {
// printf("%d ", a[i][j]);
// }
// printf("\n");
// }
// return 0;
//}