//#include<stdio.h>
//#include<string.h>
//int main()
//{
//
// char words1[105] = {0};
// char words2[105] = {0};
//
// long long int i,n;
//
// scanf("%s %s",words1,words2);
//
// if(strlen(words1)>strlen(words2))
// {
// printf("%s %s",words2,words1);
// }
// else if(strlen(words1)==strlen(words2))
// {
// for(i=0; i<strlen(words1); i++)
// {
// if(words1[i]>words2[i])
// {
// printf("%s %s",words2,words1);
// break;
// }
// else if(words1[i]<words2[i])
// {
// printf("%s %s",words1,words2);
// break;
// }
// }
// }
// else
// {
// printf("%s %s",words1,words2);
// }
//
//
//
//}
//#include<stdio.h>
//#include<string.h>
//int main(){
//
// char words1[25] = {0};
// char words2[25] = {0};
// char words3[25] = {0};
//
// int i,a,b,c;
//
// scanf("%s",words1);
// scanf("%s",words2);
// scanf("%s",words3);
//
// a=strlen(words1);
// b=strlen(words2);
// c=strlen(words3);
//
// if(words1[a-1]==words2[0] && words2[b-1]==words3[0] && words3[c-1]==words1[0]){
// printf("good");
// }
// else {
// printf("bad");
// }
//
//
// }
//#include<stdio.h>
//int main()
//{
//
// int i,j,x,y,sum=0,k=0;
// int map[27][27] = {0};
// int res[27][27] = {0};
// for(i=1; i<=25; i++)
// {
// for(j=1; j<=25; j++)
// {
// scanf("%d",&map[i][j]);
// }
// }
// for(i=1; i<=25; i++)
// {
// for(j=1; j<=25; j++)
// {
// sum=0;
// if(map[i][j]==0)
// {
// for(x=i-1; x<=i+1; x++)
// {
// for(y=j-1; y<=j+1; y++)
// {
// sum += map[x][y];
// }
// }
// if(sum==3)
// {
// res[i][j]=1;
// }
// else
// {
// res[i][j]=0;
// }
// }
// k=0;
// if(map[i][j]==1)
// {
// for(x=i-1; x<=i+1; x++)
// {
// for(y=j-1; y<=j+1; y++)
// {
// k += map[x][y];
// }
// }
// if(k>=5 || k<=2)
// {
// res[i][j]=0;
// }
// else
// {
// res[i][j]=1;
// }
// }
//
// }
// }
// for(i=1; i<=25; i++)
// {
// for(j=1; j<=25; j++)
// {
// printf("%d ",res[i][j]);
// }
// printf("\n");
// }
//
//
//
// return 0;
//
//}
//
//#include<stdio.h>
//int main()
//{
//
// int a,b,x,y,z,k,i,j,o,p,sum=0,r=0,pk;
// int map[175][175] = {0};
// int res[175][175] = {0};
//
// scanf("%d %d",&a,&b);
// scanf("%d %d %d",&x,&y,&z);
// for(i=1; i<=a; i++)
// {
// for(j=1; j<=b; j++)
// {
// scanf("%d",&map[i][j]);
// }
// }
// scanf("%d",&k);
// for(pk=0; pk< k; pk++)
// {
// for(i=1; i<=a; i++)
// {
// for(j=1; j<=b; j++)
// {
// sum=0;
// if(map[i][j]==0)
// {
// for(o=i-1; o<=i+1; o++)
// {
// for(p=j-1; p<=j+1; p++)
// {
// sum += map[o][p];
// }
// }
// if(sum==x)
// {
// res[i][j]=1;
// }
// else
// {
// res[i][j]=0;
// }
// }
// r=0;
// if(map[i][j]==1)
// {
// for(o=i-1; o<=i+1; o++)
// {
// for(p=j-1; p<=j+1; p++)
// {
// r += map[o][p];
// }
// }
// if(r<=y || r>z)
// {
// res[i][j]=0;
// }
// else
// {
// res[i][j]=1;
// }
// }
// }
// }
// for(i=1; i<=a; i++)
// {
// for(j=1; j<=b; j++)
// {
// map[i][j] = res[i][j];
// res[i][j] = 0;
// }
// }
// }
// for(i=1; i<=a; i++)
// {
// for(j=1; j<=b; j++)
// {
// printf("%d ",map[i][j]);
// }
// printf("\n");
// }
//
//
//
//
//}
//
//#include<stdio.h>
//
//int main() {
// int map[200][200] = {0};
// int res[200][200] = {0};
// int i, j, k, x, y, z, s=0, n, m, p;
// int a, b;
//
// scanf("%d %d", &a, &b);
// scanf("%d %d %d", &x, &y, &z);
//
// for(i=1; i<=a; i++){
// for(j=1; j<=b; j++) {
// scanf("%d", &map[i][j]);
// }
// }
// scanf("%d", &k);
//
// for(p=0; p<k; p++) {
// for(i=1; i<=a; i++) {
// for(j=1; j<=b; j++) {
// s=0;
// for(n=i-1; n<=i+1; n++) {
// for(m=j-1; m<=j+1; m++) {
// s+=map[n][m];
// }
// }
// if(map[i][j]==0 && s == x) {
// res[i][j] = 1;
// }
// else {
// res[i][j] = (s >= z) ? 0 : 1;
// }
// }
// }
//
// for(i=1; i<=a; i++) {
// for(j=1; j<=b; j++) {
// map[i][j] = res[i][j];
// res[i][j] = 0;
// }
// }
// }
//
// for(i=1; i<=a; i++){
// for(j=1; j<=b; j++) {
// printf("%d ", map[i][j]);
// }
// printf("\n");
// }
//
//}
//#include<stdio.h>
//
//int sum(int x, int y);
//
//int main() {
// int a, b;
//
// scanf("%d %d", &a, &b);
//
// printf("%d", sum(a, b));
//
//
//}
//
//int sum(int x, int y) {
// return x+y;
//}
//#include<stdio.h>
//void f()
//{
// printf("hello\n");
// return;
//}
//int main(){
//
// f();
// return 0;
//
// }
//#include<stdio.h>
//void f(){
//
//printf("%d",123);
//return;
//}
//int main(){
//
// f();
// return 0;
//
// }
//#include<stdio.h>
//void f(){
//
// printf("%c",'*');
// return;
// }
//int main(){
// f();
// return 0;
//
// }
//#include<stdio.h>
//void f(){
// int i;
// for(i=1; i<=2; i++){
// printf("%c",'*');
// }
// return;
// }
//int main(){
//
// f();
// return 0;
//
// }
//#include<stdio.h>
//int n, d[110];
//
//int f()
//{
// int i,max=-1;
// int loc;
// for(i=0; i<n; i++)
// {
// if(d[i]>max)
// {
// max=d[i];
// loc = i;
// }
// }
// return loc+1;
//
//}
//int main()
//{
//
// scanf("%d",&n);
//
// for(int i=0; i<n; i++)
// scanf("%d", &d[i]);
//
//
// printf("%d",f());
//
// return 0;
//
//}
//#include<stdio.h>
//
//int n;
//
//long long int d[110];
//
//long long int f()
//{
// long long int i,min=d[1];
//
// for(i=1; i<=n; i++)
// {
// if(d[i]<min)
// {
// min=d[i];
// }
// }
// return min;
//
//}
//
//int main()