/* #include<stdio.h> int main() { int a, b; scanf("%d", &a); for(; a!=0; a--) { scanf("%d", &b); printf("%d\n", b); } return 0; } */ /* #include<stdio.h> int main() {#include<stdio.h> int main() { int a,i; for(;;) { scanf("%d",&a); if(a==0) { //printf("0\n"); break; } else { printf("%d\n",a); continue; } } } int a,i; for(;;) { scanf("%d",&a); if(a==0) { //printf("0\n"); break; } else { printf("%d\n",a); continue; } } } */ /* #include<stdio.h> #include<windows.h> #include<math.h> #include<string.h> #include<conio.h> #include<stdlib.h> #define LEFT 75 #define RIGHT 77 #define UP 72 #define DOWN 80 void gotoxy(int x,int y) { COORD pos= {x,y}; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos); } int main() { int key; int x, y; x = 10; // 가로 y = 10; // 세로 gotoxy(x, y); printf("*"); while(1) { if(kbhit()) { key = getch(); switch(key) { case LEFT: gotoxy(x, y); printf(" "); x--; gotoxy(x, y); printf("*"); //printf("LEFT\n"); break; case RIGHT: gotoxy(x, y); printf(" "); x++; gotoxy(x, y); printf("*"); //printf("RIGHT\n"); break; case UP: gotoxy(x, y); printf(" "); y--; gotoxy(x, y); printf("*"); //printf("UP\n"); break; case DOWN: gotoxy(x, y); printf(" "); y++; gotoxy(x, y); printf("*"); //printf("DOWN\n"); break; } } } } */

/* #include <stdio.h> int main(void) { int month, days; printf("11"); scanf("%d", &month); switch(month) { case 2: days = 28; break; case 4: case 6: case 9: case 11: days = 30; break; default: days = 31; break; } printf("%d월의 일수는 %d입니다.\n", month, days); return 0; } */ /* #include <stdio.h> int main(void) { char op; int x, y, result; printf("수식을 입력하시오(예: 2 + 5): \n"); printf(">>10*2"); scanf("%d %c %d", &x, &op, &y); switch(op) { case '+': result = x + y; break; case '-': result = x - y; break; case '*': result = x * y; break; case '/': result = x / y; break; case '%': result = x % y; break; default: printf("10 * 2 = 20\n"); return 0; } } */ /* #include <stdio.h> int main(void) { int i = 1; loop: printf("%d * %d = %d \n", 3, i, 3 * i); i++; if(i == 10) goto end; goto loop; end: return 0; } */ /* #include <stdio.h> int main(void) { int a, b, c; printf("8 10 3"); scanf("%d %d %d", &a, &b, &c); if((a + b) > c && (b+c) > a && (a + c) > b) { printf("올바른 삼각형\n"); } else { printf("올바르지 않은 삼각형\n"); } return 0; } */ /* #include <stdio.h> int main() { char n; scanf("%d", &n); switch(n) { case 'a': case 'e': case 'i': case 'o': case 'u': printf("자음입니다."); default: printf("모음입니다."); } } */ /* #include <stdio.h> int main() { int a, b; scanf("%d %d", &a, &b); if (a%b==0) { printf("약수입니다"); } return 0; } */

/* #include <stdio.h> #define PI 3.141592 int main() { double x, y; double k; scanf("%lf", &k); x = 4 * PI * (k * k); y = 4/3.0 * PI * (k * k * k); printf("%lf %lf", x, y); } */ /* #include <stdio.h> int main(void) { int numder; printf("25"); scanf("%d", &numder); if(numder > 0) printf("양수입니다.\n"); printf("입력된 값은 %d입니다.\n", numder); return 0; } */ /* #include <stdio.h> int main(void) { int numder; printf("-5"); scanf("%d", &numder); if(numder < 0) numder = -numder; printf("5.\n", numder); return 0; } */ /* #include <stdio.h> int main(void) { int numder; printf("23"); scanf("%d", &numder); if(numder % 2 == 0) printf("입력된 정수는 짝수입니다.\n"); else printf("입력된 정수는 홀수입니다.\n"); return 0; } */ /* #include <stdio.h> int main(void) { int n, d, result; printf("분자를 입력하시오:"); scanf("%d", &n); printf("분모를 입력하시오:"); scanf("%d", &d); if(d == 0) { printf("0으로 나눌 수는 없습니다.\n"); } } */ /* #include <stdio.h> int main(void) { int year; printf("2012:"); scanf("%d", &year); if((year & 4 == 0 && year % 100 != 0) || year % 400 == 0) printf("%d년은 윤년입니다.\n", year); else printf("%d년은 윤년이 아닙니다.\n", year); return 0; } */ /* #include <stdio.h> int main(void) { int score; printf("성적을 입력하시오:"); scanf("%d", &score); if (score >= 90) printf("학점 A\n"); else if (score >= 80) printf("학점 B\n"); else if (score >= 70) printf("학점 c\n"); else if (score >= 60) printf("학점 D\n"); else printf("학점 F\n"); return 0; } */ /* #include <stdio.h> int main(void){ char ch; printf("c"); scanf("%c", &ch); if(ch >= 'A' && ch <= 'z') printf("%c는 대문자입니다.\n", ch); else if(ch >= 'a' && ch <= 'z') printf("%c는 소문자입니다.\n", ch); else if(ch >= '0' && ch <= '9') printf("%c는 숫자입니다.\n", ch); else printf("%c는 기타문자입니다.\n", ch); return 0; } */ /* #include <stdio.h> int main(void) { char op; int x, y, result; printf("수식을 입력하시오(예: 2+5)\n"); printf(">>"); scanf("%d %c %d", &x, &op, &y); if(op == '+') result = x + y; else if(op == '-') result = x - y; else if(op == '*') result = x * y; else if(op == '/') result = x / y; else if(op == '%') result = x % y; else printf("지원되지 않는 연산자입니다.\n"); printf("%d %c %d = %d \n", x, op, y, result); return 0; } */ /* #include <stdio.h> #include <math.h> int main(void) { double a, b, c, dis; printf("계수 a, 계수 b, 계수 c를 1 2 -8:"); scanf("%if %if %if", &a, &b, &c); if (a==0) printf("2.000000%f입니다.", -c / b); else { dis = b*b - 4.0*a*c; if (dis >= 0) { printf("-4.000000%f입니다.\n", (-b + sqrt(dis)) / (2.0*a)); printf("-4.000000%f입니다.\n", (-b - sqrt(dis)) / (2.0*a)); } else printf("실근이 존재하지 않습니다\n"); } } */

/* #include <stdio.h> int main(){ int a,b; scanf("%d %d", &a,&b); printf("%d", b==a); return 0; } */ /* #include <stdio.h> int main(){ double i,a,b; scanf("%if %if", &a,&b); for(i=a; i<=b; i=i+0.01) { printf("%.2lf ",i); } return 0; } */ /* #include <stdio.h> int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); if(a>b && a>c) { printf("%d\n",a); } else if(b>a && b>c) { printf("%d\n",b); } else { printf("%d\n",c); } } */ /* #include <stdio.h> int main(){ int n; scanf("%d", &n); printf("%d ", n/10); printf("%d ", n%10); } */

/* #include <stdio.h> int main(void) { printf("AND : %08X\n", 0x9 & 0xA); printf("OR : %08X\n", 0x9 | 0xA); printf("XOP : %08X\n", 0X9 ^ 0xA); printf("NOT : %08X\n", ~0x9); printf("<< : %08X\n", 0x4 << 1); printf(">> : %08\n", 0x4 >> 1); return 0; } */ /* #include <stdio.h> int main(void) { unsigned int num; printf("10진수: "); scanf("%u", &num); unsigned int mask = 1 << 7; printf("2진수: "); ((num & mask) == 0) ? printf("0") :printf("1"); mask = mask >> 1; ((num & mask) == 0) ? printf("0") : printf("1"); mask = mask >> 1; ((num & mask) == 0) ? printf("0") : printf("1"); mask = mask >> 1; ((num & mask) == 0) ? printf("0") : printf("1"); mask = mask >> 1; ((num & mask) == 0) ? printf("0") : printf("1"); mask = mask >> 1; ((num & mask) == 0) ? printf("0") : printf("1"); mask = mask >> 1; ((num & mask) == 0) ? printf("0") : printf("1"); mask = mask >> 1; ((num & mask) == 0) ? printf("0") : printf("1"); mask = mask >> 1; return 0; } */ /* #include <stdio.h> int main(void) { char data = 'a'; char key = 0xff; char encrpted_data; encrpted_data = data ^ key; printf("암호화된 문자=%c \n", encrpted_data); char orig_data; orig_data = encrpted_data ^ key; printf("원래의 데이터=%c\n", orig_data); return 0; } */ /* #include <stdio.h> int main(void) { int i; double f; f = 5 / 4; printf("%f\n", f); f = (double)5/ 4; printf("%f\n", f); f = 5.0 / 4; printf("%f\n", f); f = (double)5/ (double)4; printf("%f\n", f); i = 1.3 + 1.8; printf("%d\n", i); i = (int)1.3+ (int)1.8; printf("%d\n", i); return 0; } */ /* #include <stdio.h> int main(void) { int x=0, y=0; int result; result = 2 > 3 || 6 > 7; printf("%d\n", result); result = 2 || 3 && 3 > 2; printf("%d\n", result); result = x = y = 1; printf("%d\n", result); result = - ++x + y--; printf("%d\n", result); return 0; } */ /* #include <stdio.h> int main(void) { double f_temp; double c_temp; printf("100"); scanf("%if", &f_temp); c_temp = 5 / 9 * (f_temp - 32); printf("0.000000\n", c_temp); return 0; } */

/* #include <stdio.h> int main(){ int a,b,c,d,e ; scanf("%d %d %d %d %d", &a, &b, &c, &d, &e) printf("%d"); } */ /* #include <stdio.h> int main(void) { int x, y, result; printf("x,y"); scanf("%d %d", &x, &y); result = x + y; printf("%d + %d = %d\n", x, y, result); result = x - y; printf("%d - %d = %d\n", x, y, result); result = x * y printf("%d + %d = %d\n", x, y, result); result = x / y; printf("%d / %d = %d\n", x, y, result); result = x % y; printf("%d %% %d =%d\n", x, y, result); return 0; } */ /* #include <stdio.h> int main(void) { double x, y, result; printf("x, y"); scanf("%lf lf", &x, &y); result = x + y; printf("%f / %f = %f\n", x, y, result); result = x / y; printf("%f / %f = %f\n", x, y, result); return 0; } */ /* #include <stdio.h> #define SEC_PER_MINUTE 60 int main(void) { int input, minute, second; printf("1000"); scanf("%d", &input); minute = input / SEC_PER_MINUTE; second = input % SEC_PER_MINUTE; printf("%1000초는 16분 40초입니다\n", input, minute, second); return 0; } */ /* #include <stdio.h> int main(void) { int x=10, y=10; printf("x=%d\n", x); printf("++x의 값=%d\n", ++x); printf("x=%d\n\n",x); printf("y=%d\n", y); printf("y++의 값=%d\n", y++); printf("y=%d\n", y); return 0; } */ /* #include <stdio.h> int main(void) { int user, change = 0; int price, c5000, c1000, c500, c100; printf("3200"); scanf("%d", &price); printf("10000"); scanf("%d", &user); change = user - price; c5000 = change / 5000; change = change % 5000; c1000 = change / 1000; change = change % 1000; c500 = change / 500; change = change % 500; c100 = change / 100; change = change % 100; printf("오천원권: %d장\n", c5000); printf("천원권: %d장\n", c1000); printf("오백원 동전: %d개\n", c500); printf("백원 동전: %d개\n", c100); return 0; } */ /* #include <stdio.h> int main(void) { int x, y; x = 1; printf("수식 x+1의 값은 %d\n", x+1); printf("수식 y=x+1의 값은 %d\n", y=x+1); printf("수식 y=10+(x=2+7)의 값은 %d\n", y=10+(x=2+7)); printf("수식 y=x=3의 값은 %d\n", y=x=3)); return 0; } */ /* #include <stdio.h> int main(void) { int x = 10, y = 10, z = 33; x += 1; y *=2; z %= 10 + 20; printf("x = %d y = %d z = %d \n", x, y, z); return 0; } */ /* #include <stdio.h> int main(void) { int x, y; printf("3 4"); scanf("%d%d", &x, &y); printf("x === y의 결과값: %d\n", x == y); printf("x != y의 결과값: %d\n", x !=y); printf("X > y의 결과값: %d\n", x > y); printf("X < y의 결과값: %d\n", x < y); printf("x > y의 결과값: %d\n", x >= y); printf("x ,= y의 결과값: %d\n", x <= y); return 0; } */ /* #include <stdio.h> int main(void) { int x, y; printf("1 0"); scanf("%d%d", &x, &y); printf("%d && %d의 결과값: %d\n", x, y,x && y); printf("%d || %d의 결과값: %d\n", x || y); printf("!%d의 결과값: %d\n", x, !x); return 0; } */ /* #include <stdio.h> int main(void) { int year, result; printf("2012"); scanf("%d", &year); result = ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0); printf("result=%d \n", result); return 0; } */ /* #include <stdio.h> int main(void) { int x, y; printf("첫번째 수="); scanf("%d", &x); printf("두번째 수="); scanf("%d", &y); printf("큰 수=%d \n", (x > y) ? x : y); printf("작은 수=%d \n", (x < y) ? x : y); } */

/* #include <stdio.h> int main() { int n,m; int a[105][105]; int tt=1; scanf("%d %d", &n,&m); for(int b=0; b<m; b++) { if(b%2==0) { for(int c=n-1; c>=0; c--) { a[c][b]=tt; tt++; } } else { for(int c=0; c<=n-1; c++) { a[c][b]=tt; tt++; } } } for(int d=0; d<n; d++) { for(int e=m-1; e>=0; e--) { printf("%d ", a[d][e]); } printf("\n"); } } */ /* #include <stdio.h> int main() { int n,m; int a[105][105]; int tt=1; scanf("%d %d", &n,&m); for(int b=0; b<m; b++) { if(b%2==0) { for(int c=n-1; c>=0; c--) { a[c][b]=tt; tt++; } } else { for(int c=0; c<n; c++) { a[c][b]=tt; tt++; } } } for(int d=n-1; d>=0; d--) { for(int e=m-1; e>=0; e--) { printf("%d ", a[d][e]); } printf("\n"); } } */

/* #include<stdio.h> #include<windows.h> #include<math.h> void gotoxy(int x,int y) { COORD pos= {x,y}; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos); } int main() { int n, m; int i;*/ /* for(;;) { scanf("%d %d", &n, &m); if(n==99 && m==99) { printf("GAME OVER"); break; } printf("위치 %d에서 %d로 이동하였습니다.\n", n, m); } */ /* gotoxy(5, 5); printf("1"); gotoxy(5, 6); printf("2"); gotoxy(5, 7); printf("3"); gotoxy(5, 8); printf("4"); gotoxy(5, 9); printf("5"); } */ /* #include<stdio.h> #include<windows.h> #include<math.h> int arr[10] = {0}; void gotoxy(int x,int y) { COORD pos= {x,y}; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos); } void init() { printf("") } void draw(int x, int k) { // type here } int main() { int n,m, x; int i; init(); // 초기화 하는 함수 for(;;) { scanf("%d", &x); arr[x-1]++; } draw(x-1, arr[x-1]); } */ /* #include<stdio.h> int main() { int n,m; scanf("%d %d", &n,&m); int a[n][m]; int tt=1; for(int b=m-1; b>=0; b--) { if(b%2==0) { for(int c=n-1; c>=0; c--) { a[c][b]=tt; tt++; } } else { for(int c=0; c<=n-1; c++) { a[c][b]=tt; tt++; } } } for(int d=n-1; d>=0; d--) { for(int e=0; e<=m-1; e++) { printf("%d ", a[d][e]); } printf("\n"); } } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include<stdio.h> int rec(int n) { if(n==0) { return 0; } return n + rec(n-1); } int main() { int n; // 5 scanf("%d", &n); printf("%d", rec(n)); return 0; } */ /* #include<stdio.h> #include<windows.h> #include<math.h> void gotoxy(int x,int y) { COORD pos= {x,y}; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos); } int main() { int n, m; int i; for(;;){ scanf("%d %d", &n, &m); if(n==99 && m==99) { printf("GAME OVER"); break; } // system("cls"); // clear monitor // gotoxy(n, m); printf("위치 %d에서 %d로 이동하였습니다.\n", n, m); } gotoxy(5, 5); printf("1"); gotoxy(5, 6); printf("2"); // gotoxy < 이용한다 /* 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 */ } /*

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int n; int number(int n) { int d=0; while(n>0) { d+=n%10; n/=10; } return d; } int main() { scanf("%d",&n); n=number(n); while(n>=10) { n=number(n); } printf("%d",n); return 0; } */ /* #include<stdio.h> void rec(int n) { if(n==0) { return; } printf("%d ", n); rec(n-1); } int main() { int n; // 5 scanf("%d", &n); rec(n); } */ /* rec(n) { p(n) rec(n-1) { rec(n-2) { rec(n-3) { ... // n==0 } p(n-2); } p(n-1); } p(n); } */ /* #include<stdio.h> void rec(int n) { if(n==0) { return; } printf("%d ", n); rec(n-1); } int main() { int n; //5 scanf("%d", &n); rec(n); } */ /* #include<stdio.h> void rec(int n) { if(n==0) { return; } rec(n-1); printf("%d ", n); } int main() { int n; // 5 scanf("%d", &n); rec(n); } */ /* #include<stdio.h> void rec(int n, int m) { if(n>m) { return; } if(n%2==1) printf("%d ", n); rec(n+1, m); } int main() { int n, m; // 5 scanf("%d %d", &n, &m); rec(n, m); } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int n, d[110]; int f() { int m=0; for(int i=0; i<n; i++) { if(d[i]>m) { m=d[i]; } } for(int i=0; i<n; i++) { if(d[i]==m) { return i+1; break; } } } 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 tmp; tmp=d[1]; for(int i=2; i<=n; i++) { if(d[i]<tmp) { tmp=d[i]; } } return tmp; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%lld", &d[i]); printf("%lld", f()); return 0; } */ /* #include <stdio.h> int n; void f(int x) { if(x == 1) printf("hello\n"); else if(x == 2) printf("world\n"); else printf("\n"); } int main() { scanf("%d", &n); f(n); return 0; } */ /* #include <stdio.h> int n; void f(int k) { printf("%s\n", k%2==0?"even":"odd"); } int main() { scanf("%d", &n); f(n); return 0; } */ /* #include <stdio.h> int n; void f (int k) { if(k==0) { printf("false"); } else { printf("true"); } } int main() { scanf("%d", &n); f(n); return 0; } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int main() { int map[27][27]= {},i,j,cnt; int res[27][27] = {}; int x, y; 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++) { cnt =0; for(x=i-1; x<=i+1; x++) { for(y=j-1; y<=j+1; y++) { cnt+=map[x][y]; } } cnt -= map[i][j]; if(map[i][j]==0) { if(cnt==3) { res[i][j]=1; } } else { if(cnt==2||cnt==3) { res[i][j]=1; } else { res[i][j]=0; } } } } for(i=1; i<=25; i++) { for(j=1; j<=25; j++) printf("%d ",res[i][j]); printf("\n"); } return 0; } */ /* #include <stdio.h> void f() { printf("hello\n"); } int main() { f(); return 0; } */ /* #include <stdio.h> #include <stdio.h> void f() { printf("123"); } int main() { f(); return 0; } */ /* #include <stdio.h> #include <stdio.h> void f() { printf("*"); } int main() { f(); return 0; } */ /* #include <stdio.h> #include <stdio.h> void f() { printf("**"); } int main() { f(); return 0; } */ /* #include <stdio.h> int f() { return 'A'; } int main() { printf("%c", f()); return 0; } */ /* #include <stdio.h> int f() { return 1; } int main() { printf("%d", f()); return 0; } */ /* #include <stdio.h> long long int f() { return -2147483649LL; } int main() { printf("%lld", f()); return 0; } */ /* #include <stdio.h> float f() { return 3.14f; } int main() { printf("%f", f()); return 0; } */ /* #include <stdio.h> double f() { return 3.1415926535897; } int main() { printf("%.13lf", f()); return 0; } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int main() { int map[27][27]= {},i,j,cnt; int res[27][27] = {}; 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++) { cnt=map[j-1][j-1]+map[j-1][j]+map[j-1][j+1]+map[i][j-1]+map[i][j+1]+map[i+1][j-1]+map[i+1][j]+map[i+1][j+1]; if(map[i][j]==0) { if(cnt==3) { res[i][j]=1; } } else { if(cnt==2||cnt==3) { continue; } else { map[i][j]=0; } } } for(i=1; i<=25; i++) { for(j=1; j<=25; j++) printf("%d ",res[i][j]); printf("\n"); } } return 0; } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int main() { int a[101][101]= {}; int n=0, m=0; int j, k; int cnt=1; scanf("%d %d",&n, &m); if(n==1 && m==1) { printf("1"); return 0; } j=0; k=0; while( a[k][j] == 0 ) { while(j < m && a[k][j] == 0) { a[k][j++]=cnt++; } j--; k++; while(k < n && a[k][j] == 0) { a[k++][j]=cnt++; } k--; j--; while(j >= 0 && a[k][j] ==0) { a[k][j--]=cnt++; } j++; k--; while(k >= 0 && a[k][j] == 0 ) { a[k--][j]=cnt++; } k++; j++; } for(j = 0 ; j < n ; j++) { for(k = 0 ; k < m ; k++) { printf("%d ",a[j][k]); } printf("\n"); } return 0; } */ /* #include<stdio.h> int main() { int n, m, k=1, i, j; int dt=0; int x=1, y=1; int direct[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int map[105][105] = {0}; scanf("%d %d", &n, &m); for(i=0; i<=n+1; i++) { for(j=0; j<=m+1; j++) { if(i==0 || j==0 || i==n+1 || j==m+1) { map[i][j] = 1; } } } map[x][y] = k++; for(i=1; i<n*m; i++) { if(map[x+direct[dt][0]][y+direct[dt][1]]==0){ x+=direct[dt][0]; y+=direct[dt][1]; map[x][y] = k++; } else { dt++; dt %= 4; i--; } } for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { printf("%d ", map[i][j]); } printf("\n"); } return 0; } */ /* #include<stdio.h> int main() { int n, m, k=1, i, j; int dt=0; int x=1, y=1; int direct[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int map[105][105] = {0}; scanf("%d %d", &n, &m); for(i=0; i<=n+1; i++) { for(j=0; j<=m+1; j++) { if(i==0 || j==0 || i==n+1 || j==m+1) { map[i][j] = 1; } } } k=n*m; map[x][y] = k--; for(i=1; i<n*m; i++) { if(map[x+direct[dt][0]][y+direct[dt][1]]==0) { x+=direct[dt][0]; y+=direct[dt][1]; map[x][y] = k--; } else { dt++; dt %= 4; i--; } } for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { printf("%d ", map[i][j]); } printf("\n"); } return 0; } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int main() { int map[101][101] = {0}; int i, j, n, m, k =1; scanf("%d %d", &n,&m); for(i=0; i<n; i++) { if(i%2==0) { for(j=0; j<m; j++) { map[i][j] =k++; } } else { for(j=m-1; j>=0; j--) { map[i][j] =k++; } } } for(i=n-1; i>=0; i--) { for(j=m-1; j>=0; j--) { printf("%d ", map[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int map[101][101] = {0}; int i, j, n, m, k =1; scanf("%d %d", &n,&m); for(i=0; i<n; i++) { if(i%2==0) { for(j=0; j<m; j++) { map[i][j] =k++; } } else { for(j=m-1; j>=0; j--) { map[i][j] =k++; } } } for(i=n-1; i>=0; i--) { for(j=0; j<m; j++) { printf("%d ", map[i][j]); } printf("\n"); } return 0; } */ /* #include<stdio.h> int main() { int i,j,h,w,n,d,l,x,y,a[101][101]= {}; scanf("%d %d",&h,&w); scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d %d %d %d",&l,&d,&x,&y); for(j=0; j<l; j++) { if(d==0) a[x][y+j]=1; else a[x+j][y]=1; } } for(i=1; i<=h; i++) { for(j=1; j<=w; j++) { printf("%d ",a[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int arr[15][15]= {0}; int i, j; for (i = 1; i <= 10; i ++) { for (j = 1; j <= 10; j ++) { scanf("%d", &arr[i][j]); } } int x = 2, y = 2; if(arr[x][y] == 2) { arr[x][y] = 9; } else { arr[x][y] = 9; while (1) { if (arr[x][y + 1] == 0) { arr[x][y + 1] = 9; y ++; } else if (arr[x][y + 1] == 1) { if (arr[x + 1][y] == 1) break; else if (arr[x + 1][y] == 0) { arr[x + 1][y] = 9; x ++; } else if (arr[x + 1][y] == 2) { arr[x + 1][y] = 9; break; } } else if (arr[x][y + 1] == 2) { arr[x][y + 1] = 9; break; } if (x == 8 && y == 8) break; } } for (i = 1; i <= 10; i ++) { for (j = 1; j <= 10; j ++) { printf("%d ", arr[i][j]); } printf("\n"); } } */

/* #include <stdio.h> int main() { int map[101][101] = {0}; int i, j, n, m, k =1; scanf("%d", &n); for(i=0; i<n; i++) { if(i%2==0) { for(j=0; j<n; j++) { map[i][j] = k++; } } else { for(j=n-1; j>=0; j--) { map[i][j] = k++; } } } for(i=n-1; i>=0; i--) { for(j=0; j<n; j++) { printf("%d ", map[j][i]); } printf("\n"); } return 0; } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int main() { int a[11][10],i,j,n=0; for(i=0; i<11; i++) { for(j=0; j<10; j++) { scanf("%d",&a[i][j]); } } for(i=0; i<10; i++) { if(a[10][i]==1) { n=0; for(j=9; j>=0; j--) { if(a[j][i]>0) { printf("%d crash\n",i+1); break; } else if(a[j][i]<0) { printf("%d fall\n",i+1); break; } n++; if(n==10) { printf("%d safe\n",i+1); } } } } return 0; } */ /* #include<stdio.h> int main() { int map[100][100] = {0}; int i, j, n, k = 1; scanf("%d", &n); for(i=0; i<n; i++) { if(i%2==0) { for(j=0; j<n; j++) { map[i][j] = k++; } } else { for(j=n-1; j>=0; j--) { map[i][j] = k++; } } } for(i=0; i<n; i++) { for(j=0; j<n; j++) { printf("%d ", map[i][j]); } printf("\n"); } return 0; } */ /* #include<stdio.h> int main() { int map[100][100] = {0}; int i, j, n, k = 1; scanf("%d", &n); for(i=0; i<n; i++) { if(i%2==0) { for(j=0; j<n; j++) { map[i][j] = k++; } } else { for(j=n-1; j>=0; j--) { map[i][j] = k++; } } } for(i=0; i<n; i++) { for(j=n-1; j>=0; j--) { printf("%d ", map[i][j]); } printf("\n"); } return 0; } */ /* #include<stdio.h> int main() { int map[101][101] = {0}; int i, j, n, m, k =1; scanf("%d", &n); for(i=0; i<n; i++) { if(i%2==0) { for(j=0; j<n; j++) { map[i][j] = k++; } } else { for(j=n-1; j>=0; j--) { map[i][j] = k++; } } } for(i=0; i<n; i++) { for(j=0; j<n; j++) { printf("%d ", map[j][i]); } printf("\n"); } return 0; } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include <stdio.h> int main() { int A[101][101]= {0}; int x=0,y,t=2,a,b,n; scanf("%d",&n); A[0][n/2]=1; y=n/2; if(n!=1) while(1) { a=x; b=y; x=x-1; y=y+1; if(x<0) { x=n-1; } if(y>n-1) { y=0; } if((A[x][y])!=0) { y=b; x=a+1; } A[x][y]=t; t++; if(t==(n*n)+1) { break; } } for(x=0; x<n; x++) { for(y=0; y<n; y++) { printf("%d ",A[x][y]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n, i, j, x, y; int a[20][20]= {}; for(i=1; i<=19; i++) for(j=1; j<=19; j++) scanf("%d", &a[i][j]); scanf("%d", &n); for(i=1; i<=n; i++) { scanf("%d %d", &x, &y); for(j=1; j<=19; j++) { if(a[x][j]==0) a[x][j]=1; else a[x][j] = 0; } for(j=1; j<=19; j++) { if(a[j][y]==0) a[j][y]=1; else a[j][y] = 0; } } for(i=1; i<=19; i++) { for(j=1; j<=19; j++) { printf("%d ",a[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int a[11][11]= {0},r,c,sum = 0,i,j; 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("-1"); else { sum+=(a[r-1][c-1]+a[r-1][c]+a[r-1][c+1]); sum+= (a[r][c-1]+a[r][c+1]); sum+= (a[r+1][c-1]+a[r+1][c]+a [r+1][c+1]); printf("%d",sum); } return 0; } */

/* #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; } */ /* #include<stdio.h> int main() { int i,j,b=0,c=1,x,y,e; int n; int a[110][110] = {0}; scanf("%d",&n); scanf("%d %d",&x,&y); e=x; a[x-1][y-1]=1; for(i=0; i<n; i++) { b++; c++; for(j=0; j<n; j++) { a[x-1][y-b-1]=c; a[x-1][y+b-1]=c; } } for(i=x; i<n; i++) { for(j=0; j<n; j++) { a[i][j]=a[i-1][j]+1; } } x=e-1; for(i=x-1; i>=0; i--) { for(j=0; j<n; j++) { a[i][j]=a[i+1][j]+1; } } 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 i, j, n, k, x, y; scanf("%d", &n); scanf("%d %d", &x, &y); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { k = 0; if(i<x) k += (x-i); else k += (i-x); if(j<y) k += (y-j); else k += (j-y); printf("%d ", k + 1); } printf("\n"); } } */ /* #include<stdio.h> int main() { int n, a[19][19]= {}, i, j, b, c; scanf("%d", &n); for(i=0; i<n; i++) { scanf("%d %d", &b, &c); a[b-1][c-1]=1; } for(i=0; i<19; i++) { for(j=0; j<19; j++) { printf("%d ", a[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int arr[121][121],i,j,k; scanf("%d",&k); for(i=1; i<=k; i++) { scanf("%d",&arr[i][1]); } for(i=2; i<=k; i++) { for(j=2; j<=k; j++) { arr[i][j] = arr[i][j-1] - arr[i-1][j-1]; } } for(i=1; i<=k; i++) { for(j=1; j<=i; j++) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int A[101][101]= {0}; int x=0,y,t=2,a,b,n; scanf("%d",&n); A[0][n/2]=1; y=n/2; while(1) { a=x; b=y; x=x-1; y=y+1; if(x<0) { x=n-1; } if(y>n-1) { y=0; } if((A[x][y])!=0) { y=b; x=a+1; } A[x][y]=t; t++; if(t==(n*n)+1) { break; } } for(x=0; x<n; x++) { for(y=0; y<n; y++) { printf("%d ",A[x][y]); } printf("\n"); } return 0; } */

/* #include <stdio.h> int main() { int n, m, i, j, k = 1; int arr[101][101] = {0}; scanf("%d %d", &n, &m); for(int i=m; i>=1; i--) { for(int j=n; j>=1; j--) { arr[j][i] = k++; } } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { printf("%d ", arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int map[101][101] = {0}; int i, j, n, m, k = 1, sum = 0; scanf("%d", &n); for(i=0; i<n; i++) { for(j=0; j<n; j++) { map[i][j] = k++; } } for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(i == 0||j == 0 || j == n-1 || i == n-1) { sum += map[i][j]; } } } printf("%d",sum); return 0; } */