/* #include <stdio.h> typedef struct { int num; int m; }gas; int main() { gas st[101],temp; int n,a,b,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d %d",&st[i].num,&st[i].m); } for(i=1;i<n;i++) { for(j=1;j<=n-i;j++) { if(st[j].num>st[j+1].num) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } for(i=1;i<=n;i++) { printf("%d %d\n",st[i].num,st[i].m); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j,temp,c=0;; int a[1001]; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } if(n==2) { if(a[1]<a[2]) { printf("0"); return 0; } else { printf("1"); return 0; } } for(i=1;i<n;i++) { c=0; for(j=1;j<=n-i;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; c++; } } if(c==0) { printf("%d",i-1); return 0; } } } */ /* #include <stdio.h> typedef struct { char name[10]; int g; } student; int main() { student st[101],temp; int n,m,i,j; scanf("%d %d ",&n,&m); for(i=1; i<=n; i++) { scanf("%s %d",st[i].name,&st[i].g); } for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if(st[j].g<st[j+1].g) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } for(j=1; j<=m; j++) { printf("%s\n",st[j].name); } return 0; } */ /* #include <stdio.h> int a[100001]; void swap(int pivot, int high) { int temp; temp=a[pivot]; a[pivot]=a[high]; a[high]=temp; return ; } void quick_sort(int s, int e) { int pivot=s, low=s, high=e+1; if(s>=e) return ; do { do { low++; }while(a[pivot]>a[low]); do { high--; }while(a[pivot]<a[high]); if(low<high) { swap(low,high); } }while(low<high); swap(pivot,high); quick_sort(s,high-1); quick_sort(high+1,e); } int main() { int n,i; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } quick_sort(1,n); for(i=1;i<=n;i++) { printf("%d\n",a[i]); } return 0; } */ /* #include <stdio.h> typedef struct { char name[100]; int ss; } s; int main() { s st[101],temp; int n,i,j,y,m,d; scanf("%d ",&n); for(i=1; i<=n; i++) { scanf("%s %d %d %d",st[i].name,&y,&m,&d); st[i].ss=y*10000+m*100+d; } for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if(st[j].ss>st[j+1].ss) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } else if(st[j].ss==st[j+1].ss) { if(strcmp(st[j].name,st[j+1].name)>0) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } } for(i=1; i<=n; i++) { printf("%s\n",st[i].name); } return 0; } */ /* #include <stdio.h> typedef struct { int nn; int g; int in; } math; int main() { math st[1001],temp; int m,n,i,j; scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d %d",&st[i].g,&st[i].in); st[i].nn=i; } for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if(st[j].g<st[j+1].g) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } else if(st[j].g==st[j+1].g) { if(st[j].in<st[j+1].in) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } } for(i=1;i<=n;i++) { printf("%d %d %d\n",st[i].nn,st[i].g,st[i].in); } return 0; } */ /* #include <stdio.h> typedef struct { char name[10]; int g; }student; int main() { student st[51],temp; int n,i,j; scanf("%d ",&n); for(i=1;i<=n;i++) { scanf("%s %d",st[i].name,&st[i].g); } for(i=1;i<n;i++) { for(j=1;j<=n-i;j++) { if(st[j].g>st[j+1].g) { temp=st[j]; st[j]=st[j+1]; st[j+1]=temp; } } } printf("%s",st[n-2].name); return 0; } */ /* #include <stdio.h> int main() { int a[8]; int i,j,temp; for(i=1;i<=7;i++) { scanf("%d",&a[i]); } for(i=1;i<7;i++) { for(j=1;j<=7-i;j++) { if(a[j]<a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(i=1;i<=2;i++) { printf("%d\n",a[i]); } return 0; } */

/* #include <stdio.h> #include <string.h> char stack1[101]={},stack2[101]={}; int stack3[102]={}; int top1=-1,top2=-1,top3=-1; void push(int data) { stack3[++top3]=data; } char pop1() { return stack1[top1--]; } char pop2() { return stack2[top2--]; } int pop3() { return stack3[top3--]; } int main() { char str1[101],str2[101]; int i,num=0,c=0; int a,b,p,q; scanf("%s %s",str1,str2); a=strlen(str1); b=strlen(str2); for(i=0; i<a; i++) { stack1[++top1]=str1[i]; } for(i=0; i<b; i++) { stack2[++top2]=str2[i]; } while(top1!=-1||top2!=-1) { num=c; if(top1!=-1) num+=pop1()-48; if(top2!=-1) num+=pop2()-48; push(num%10); c=num/10; } if(c!=0) push(c); while(top3!=-1) { printf("%d",pop3()); } return 0; } */ /* #include <stdio.h> int stack[201]; int top=-1; void push(int data) { stack[++top]=data; } int pop() { return stack[top--]; } int main() { char str[201]= {}; int i,a=0,b=0,c=0; gets(str); for(i=0; str[i]!=NULL; i++) { if(str[i]>=48&&str[i]<=57) { if(str[i+1]==32) { c+=str[i]-48; push(c); c=0; } else { c=c*10+(str[i]-48)*10; } } else if(str[i]>=33&&str[i]<=47) { if(str[i]=='*') { push(pop()*pop()); } if(str[i]=='+') { push(pop()+pop()); } if(str[i]=='-') { a=pop(); b=pop(); push(b-a); } } } printf("%d",pop()); return 0; } */ /* #include <stdio.h> int stack[201]; int top=-1; void push(int data) { stack[++top]=data; } int pop() { if(top==-1) return 0; return stack[top--]; } int main() { int n,i,j=0,sum=0,c=0; char str[50]; scanf("%d ",&n); for(i=0; i<n; i++) { gets(str); if(str[1]=='u') { for(j=6;str[j]!=' ';j++) { c=c*10+str[j]-48; } push(c); c=0; } else if(str[0]=='t') { if(top==-1) printf("-1\n"); else printf("%d\n",stack[top]); } else if(str[0]=='p') { pop(); } else if(str[0]=='s') { printf("%d\n",top+1); } else if(str[0]=='e') { if(top==-1) { printf("true\n"); } else { printf("false\n"); } } } return 0; } */ /* #include <stdio.h> void f(int n) { if(n==0) return ; f((n-1)/26); printf("%c",(n-1)%26+65); } int main() { int n; scanf("%d",&n); f(n); return 0; } */ /* #include <stdio.h> int a[10001]; int n, i, j, temp; int main() { scanf("%d", &n); for (i=1; i<=n; i++) scanf("%d", &a[i]); for(i=1; i<n; i++) { for(j=1; j<=n-i; j++) { if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } for (i = 1; i <= n; i++) printf("%d\n", a[i]); return 0; } */ /* #include <stdio.h> int a[10001]; int n, i, j, temp, min; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i=1; i<n; i++) { min=i; for (j=i+1; j<=n; j++) { if(a[min]>a[j]) { min=j; } } temp = a[i]; a[i] = a[min]; a[min] = temp; } for (i=1; i<=n; i++) printf("%d\n", a[i]); return 0; } */ /* #include <stdio.h> int a[10001]; int n, i, j, temp, key; int main() { scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[i]); for (i=2; i<=n; i++) { key=a[i]; for(j=i-1;j>0&&key<a[j];j--) { a[j+1]=a[j]; } a[j+1]=key; } for (i=1; i<=n; i++) printf("%d\n", a[i]); return 0; } */ /* #include <stdio.h> int a[101]; int n,i,j,max=0,temp=0; int main() { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=n;i>=2;i--) { max=i; for(j=i-1;j>=1;j--) { if(a[max]>a[j]) { max=j; } } temp=a[i]; a[i]=a[max]; a[max]=temp; } for(i=1;i<=n;i++) { printf("%d ",a[i]); } return 0; } */

/* #include <stdio.h> int memo[51][51]={}; int f(int r, int c) { if(memo[r][c]!=0) return memo[r][c]; if(r==1||c==1) memo[r][c]=1; else memo[r][c]=(f(r-1,c)+f(r,c-1))%100000000; return memo[r][c]; } int main() { int r,c; scanf("%d %d",&r,&c); printf("%d",f(r,c)); return 0; } */ /* #include <stdio.h> int memo[201]={}; int f(int n) { if(memo[n]!=0) return memo[n]; if(n<=2) memo[n]=1; else memo[n]=(f(n-1)+f(n-2))%10009; return memo[n]; } int main() { int n; scanf("%d",&n); printf("%d",f(n)); return 0; } */ /* #include <stdio.h> int memo[100001]={}; int f(int n) { if(memo[n]!=0) return memo[n]; if(n==1) memo[n]=1; else if(n==2) memo[n]=2; else if(n==3) memo[n]=4; else memo[n]=(f(n-3)+f(n-2)+f(n-1))%1000; return memo[n]; } int main() { int n; scanf("%d",&n); printf("%d",f(n)); return 0; } */ /* #include <stdio.h> int stack[100]; int top=-1; //마지막으로 데이터가 들어온 곳의 위치 void push(int data) { stack[++top]=data; } int pop() { return stack[top--]; } int main() { push(1); push(4); push(2); printf("%d",pop()); } */ /* #include <stdio.h> char stack[201]; int top=-1; void push(char data) { stack[++top]=data; } char pop() { return stack[top--]; } int main() { char str[201]; int n,i; scanf("%d",&n); scanf("%s",str ); for(i=n-1; i>=0; i--) { push(str[i]); } for(i=0; i<n; i++) { if(top%3==2&&i!=0) printf(","); printf("%c",pop()); } return 0; } */ /* #include <stdio.h> int stack[100001]; int top=-1; //top : 마지막으로 입력된 데이터의 위치 void push(int data) { stack[++top]=data; } int pop() { return stack[top--]; } void view() { printf("stack : "); for(int i=0;i<=top;i++) { printf("%d ",stack[i]); } printf("\n"); } int main() { int k,i,a,sum=0; scanf("%d",&k); for(i=k;i>=1;i--) { scanf("%d",&a); if(a!=0) { push(a); } else { pop(); } view(); } while(top!=-1) { sum+=pop(); } printf("%d",sum); return 0; } */ /* #include <stdio.h> int top=0; int main() { int i; char str[50001]; scanf("%s",str); for(i=0;str[i]!=NULL;i++) { if(str[i]=='(') top++; else { top--; if(top<0) { printf("bad"); return 0; } } } if(top!=0) { printf("bad"); } else { printf("good"); } return 0; } */ /* #include <stdio.h> int top=0; int main() { char str[100001]; int i,sum=0; scanf("%s",str); for(i=0;str[i]!=NULL;i++) { if(str[i]=='('&&str[i+1]==')') sum+=top; else if(str[i]=='(') top++; else if(str[i]==')'&&str[i-1]!='(') { top--; sum++; } } printf("%d",sum); return 0; } */ /* #include <stdio.h> char stack1[101],stack2[101]; int top1=-1,top2=-1; void push(char data) { } char pop() { return stack[top1--]; } char pop1() { return stack[top2--]; } int main() { char str1[101],str2[101]; int i,num,c=0; scanf("%s %s",str1,str2); for(i=strlen(str1)-1; i>0; i--) { stack1[++top1]=str1[i]; } for(i=strlen(str2)-1; i>0; i--) { stack2[++top2]=str2[i]; } while(top1!=-1||top2!=-1) { num=c+pop()+pop1()-96; push(num%10); c=num/10; } }*/

/* #include <stdio.h> int n, a, b, d[1010]; int maxi() { int max=0,c=a; max=d[a]; for(int i=a;i<=b;i++) { if(max<d[i]) { max=d[i]; c=i; } } return c; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d%d", &a, &b); printf("%d\n", maxi(a, b)); } */ /* #include <stdio.h> int n, k, d[1010]; int lower_bound() { int c=0; for(int i=1;i<=n;i++) { if(k>d[i]) { c=i; } } c+=1; return c; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d", &k); printf("%d\n", lower_bound(k)); } recursive function 재귀함수 f(n) : n부터 1까지 출력하는 함수 n출력 -> n-1부터 1까지 출력 n 출력 -> f(n-1) g(n) : 1부터 n까지 출력하는 함수 1부터 n-1까지 출력 -> n출력 g(n-1) -> n출력 */ /* #include <stdio.h> void f(int n) { if(n==0) return ; //종료조건 printf("%d\n",n); f(n-1); //재귀호출 } int main() { f(10); return 0; } */ /* #include <stdio.h> void f(int n) { if(n==0) return ; f(n-1); printf("%d\n",n); return ; } int main() { int n; scanf("%d",&n); f(n); return 0; } */ /* #include <stdio.h> int n; void f(n) { if(n==0) return ; printf("%d\n",n); f(n-1); return ; } int main() { scanf("%d",&n); f(n); return 0; } */ /* #include <stdio.h> void f(int a,int b) { if(b==a-1) return ; f(a,b-1); if(b%2!=0) printf("%d ",b); return ; } int main() { int a,b; scanf("%d %d",&a,&b); f(a,b); return 0; } f(n) : return (1+2+3+4+ ...+n); : return (1+2+3+....+n-1 + n); : return f(n-1)+n; */ /* #include <stdio.h> int f(int n) { if(n==1) return 1; return f(n-1)+n; } int main() { int n; scanf("%d",&n); printf("%d",f(n)); return 0; } */ /* #include <stdio.h> long long int f(int n) { if(n==1) return 1; return f(n-1)*n; } int main() { int n; scanf("%d",&n); printf("%lld",f(n)); return 0; } */ /* #include <stdio.h> int f(int n) { if(n==1||n==2) return 1; return f(n-1)+f(n-2); } int main() { int n; scanf("%d",&n); printf("%d",f(n)); return 0; } */ /* #include <stdio.h> void f(int n) { if(n==1) return 1; else if(n%2==0) { printf("%d\n",n/2); f(n/2); return ; } else { printf("%d\n",3*n+1); f(3*n+1); return ; } } int main() { int n; scanf("%d",&n); printf("%d\n",n); f(n); return 0; } */ /* #include <stdio.h> void f(int n) { if(n==1) return 1; else if(n%2==0) { f(n/2); printf("%d\n",n/2); return ; } else { f(3*n+1); printf("%d\n",3*n+1); return ; } } int main() { int n; scanf("%d",&n); f(n); printf("%d",n); return 0; } */ /* #include <stdio.h> void f(int n) { if(n==0) return ; printf("*"); f(n-1); return ; } void g(int n) { if(n==0) return ; g(n-1); f(n); printf("\n"); return ; } int main() { int n; scanf("%d",&n); g(n); return 0; } */ /* #include <stdio.h> int f(int n) { if(n==1||n==0) { printf("%d",n); return ; } f(n/2); printf("%d",n%2); return ; } int main() { int n; scanf("%d",&n); f(n); return 0; } */ /* #include <stdio.h> int memo[22][22]={}; int SuperSum(int k,int n) { if(memo[k][n]!=0) return memo[k][n]; if(k==0) return memo[0][n]=n; if(n==1) return memo[k][1]=1; return memo[k][n]=SuperSum(k,n-1)+SuperSum(k-1,n); } int main() { int k,n; while( scanf("%d %d", &k, &n) != EOF ) printf("%d\n", SuperSum(k, n)); return 0; } */

/* #include <stdio.h> typedef struct { char name[20]; int s1; int s2; int s3; }student; int main() { student st[101]; int n,i,a,b,c,max=1; scanf("%d",&n); b=n; c=n; for(i=1;i<=n;i++) { scanf("%s %d %d %d",st[i].name,&st[i].s1,&st[i].s2,&st[i].s3); } for(i=1;i<=n;i++) { if(max<st[i].s1) { max=st[i].s1; a=i; } } for(i=1;i<=n;i++) { if(st[a].s2>=st[i].s2&&a!=i) { b--; } if(st[a].s3>=st[i].s3&&a!=i) { c--; } } printf("%s %d %d",st[a].name,b,c); return 0; } #include <stdio.h> typedef struct { int s; int r; }student; int main() { student st[201]; int n,i,j,grade=1; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&st[i].s); } for(i=1;i<=n;i++) { grade=1; for(j=1;j<=n;j++) { if(st[i].s<st[j].s) { grade++; } } st[i].r=grade; printf("%d %d\n",st[i].s,st[i].r); } return 0; } */ //function : 명령의 집합 //#include <stdio.h> //int i; //global /* 반환형 함수이름(매개변수) { return (반환형과 같은 변수); } void f() { int i; for(i=1;i<=3;i++) { printf("*"); } return ; }//no input , no output void f(int n) { int i; for(i=1;i<=n;i++) { printf("*"); } printf("\n"); }// input, no output int main() { // int i; //local f(6); printf("hello world\n"); f(7); return 0; } char mysum(int a, int b) { return a+b; } //input o output o int main() { // int n; // n=mysum(5,6); // printf("%d",n); printf("%c",mysum(5,6)); return 0; } */ /* #include <stdio.h> void f() { printf("hello"); return ; } int main() { f(); return 0; } */ /* #include <stdio.h> char f() { return 'A'; } int main() { printf("%c", f() ); return 0; } */ /* #include <stdio.h> int n; void f(int n) { if(n==1) { printf("hello"); } else if(n==2) { printf("world"); } return ; } int main() { scanf("%d", &n); f(n); return 0; } */ /* #include <stdio.h> int n; void f(int n) { int i; for(i=1;i<=n;i++) { printf("*"); } return ; } int main() { scanf("%d", &n); f(n); return 0; } */ /* #include <stdio.h> int n; char grade(int n) { if(n>=90) { return 'A'; } if(n>=80) { return 'B'; } if(n>=70) { return 'C'; } if(n>=60) { return 'D'; } else { return 'F'; } } int main() { scanf("%d", &n); printf("%c", grade(n)); return 0; } */ /* #include <stdio.h> long long int n; long long int abs(long long int n) { if(n<0) { n=-n; } return n; } int main() { scanf("%lld", &n); printf("%lld\n", abs(n)); return 0; } */ /* #include <stdio.h> int n, a, b, d[1010]; long long int subsetsum(int a, int b) { long long int sum=0; for(int i=a;i<=b;i++) { sum+=d[i]; } return sum; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d%d", &a, &b); printf("%lld\n", subsetsum(a, b)); } */ /* #include <stdio.h> int n, k, d[1010]; int upper_bound(int k) { int a=0; for(int i=1;i<=n;i++) { if(d[i]<=k) { a++; } if(a==n) { a=n; } } a++; return a; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d", &k); printf("%d\n", upper_bound(k)); } */ /* #include <stdio.h> typedef struct { int c; int n; int g; }z; int main() { z st[101]; int n,i; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d %d %d",st[i].c,st[i].g,st[i].n) } }*/ /* #include <stdio.h> int n; long long int d[110]; long long int f() { long long int min=d[1]; for(int i=1; i<=n; i++) { if(min>d[i]) { min=d[i]; } } return min; } 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; long long int f(int n) { long long int sum=0; for(int i=1;i<=n;i++) { sum+=i; } return sum; } int main() { scanf("%d", &n); printf("%lld\n", f(n)); } */ /* #include <stdio.h> int gcd(int p, int q) { if(p==0) return q; return gcd(q%p, p); } long long int lcm(int a, int b) { return (long long int)a*b/gcd(a,b); } int main() { int a, b; scanf("%d%d", &a, &b); printf("%lld\n", lcm(a, b)); } */ /* #include <stdio.h> int a, n; long long int pow(int a, int n) { long long int p=1; if(a==1) { return 1; } else { for(int i=1; i<=n; i++) { p=p*a; } return p; } } int main() { scanf("%d%d", &a, &n); printf("%lld\n", pow(a, n)); } */

/* #include <stdio.h> int main() { int h,w,n,l,d,x,y,i,j,k; int arr[101][101]= {}; scanf("%d %d %d",&h,&w,&n); for(i=1; i<=n; i++) { scanf("%d %d %d %d",&l,&d,&x,&y); if(d==1) { for(k=x; k<=x+l-1; k++) { arr[k][y]=1; } } else { for(k=y; k<=y+l-1; k++) { arr[x][k]=1; } } } for(k=1; k<=h; k++) { for(j=1; j<=w; j++) { printf("%d ",arr[k][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,l,x[9],y[9],i,j,k,b; int arr[11][11]= {}; for(i=1; i<=10; i++) { for(j=1; j<=10; j++) { scanf("%d",&arr[i][j]); } } for(i=1; i<=10; i++) { for(j=1; j<=10; j++) { if(arr[i][j]>0) { b=arr[i][j]; for(k=i+1; k<=i+b; k++) { if(k>10 ||arr[k][j]==-1) break; if(arr[k][j]==0) arr[k][j]=-2; } for(k=i-1; k>=i-b; k--) { if(k<1 ||arr[k][j]==-1) break; if(arr[k][j]==0) arr[k][j]=-2; } for(k=j+1; k<=j+b; k++) { if(k>10 ||arr[i][k]==-1) break; if(arr[i][k]==0) arr[i][k]=-2; } for(k=j-1; k>=j-b; k--) { if(k<1 ||arr[i][k]==-1) break; if(arr[i][k]==0) arr[i][k]=-2; } arr[i][j]=-2; } } } scanf("%d",&n); for(l=1; l<=n; l++) { scanf("%d %d",&x[l],&y[l]); if(arr[x[l]][y[l]]==0) { arr[x[l]][y[l]]=l; } } for(i=1; i<=10; i++) { for(j=1; j<=10; j++) { printf("%d ",arr[i][j]); } printf("\n"); } printf("Character Information\n"); for(l=1; l<=n; l++) { if(arr[x[l]][y[l]]<0) { printf("player %d dead\n",l); } else { printf("player %d survive\n",l); } } return 0; } */ /* #include <stdio.h> #include <string.h> int main() { int n,a=0,i,j; int arr1[10]={9,0,1,2,3,4,5,6,7,8}; char strA[12]={'L','A','B','C','D','E','F','G','H','I','J','K'}; scanf("%d",&n); a=(n%60)-3; printf("%c%d",strA[a%12],arr1[a%10]); return 0; } */ #include <stdio.h> typedef struct { char name[20]; int s1; int s2; int s3; }student; int main() { student st[100]; int n,i,j,a=2,max=1; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s %d %d %d",st[i].name,&st[i].s1,&st[i].s2,&st[i].s3); } for(i=1;i<=n;i++) { if(max<st[i].s1) { max=st[i].s1; a++; } max=1; if(max<st[i].s2) { max=st[i].s2; } } printf("%s %d %d",st[a].name,st[a].s2,st[a].s3); return 0; }

/* #include <stdio.h> int main() { int n,i=0,j=0,k=1; int arr[50][50]={}; scanf("%d",&n); i=1; j=n/2+1; while(k<=n*n) { arr[i][j]=k++; if(arr[i][j]%n==0) { i++; continue; } if(i==1) { 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"); } return 0; } */ /* #include <stdio.h> int main() { int n,x,y,i,j,k=1; int arr[101][101]; scanf("%d %d %d",&n,&x,&y); for(i=x; i<=n; i++) { if(i==x) { for(j=y; j<=n; j++) { arr[i][j]=k++; } k=2; for(j=y-1; j>=1; j--) { arr[i][j]=k++; } continue; } for(j=1; j<=n; j++) { arr[i][j]=arr[i-1][j]+1; } } for(i=x-1; i>=1; i--) { for(j=1; j<=n; j++) { arr[i][j]=arr[i+1][j]+1; } } 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 r,c,i,j,a=0; int arr[11][11]={}; for(i=1; i<=9; i++) { for(j=1; j<=9; j++) { scanf("%d ",&arr[i][j]); } } scanf("%d %d",&r,&c); for(i=r-1; i<=r+1; i++) { for(j=c-1; j<=c+1; j++) { if(arr[i][j]==1) { a++; } } } if(arr[r][c]==1) { printf("-1"); } else { printf("%d",a); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j,a=0,b=0,sum=0,c; int arr[27][27]= {}; for(i=1; i<=25; i++) { for(j=1; j<=25; j++) { scanf("%d",&arr[i][j]); } } for(i=1; i<=25; i++) { for(j=1; j<=25; j++) { sum=0; for(a=i-1; a<=i+1; a++) { for(b=j-1; b<=j+1; b++) { if(arr[a][b]==1) { sum++; } } } c=arr[i][j]; if(arr[i][j]==0) { if(sum==3) { c=1; } } else { if(sum<=2||sum>=5) { c=0; } } printf("%d ",c); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; int arr[11][11]={}; for(i=1;i<=10;i++) { for(j=1;j<=10;j++) { scanf("%d",&arr[i][j]); } } i=2;j=2; while(1) { if(arr[i][j]==2) { arr[i][j]=9; break; } else if(arr[i][j]==0) { arr[i][j]=9; } if(arr[i][j+1]!=1) { j++; } else if(arr[i+1][j]!=1) { i++; } else { break; } } 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 n,x,y,i,j,k,sum=0; int arr[101][101]={}; scanf("%d",&n); for(k=1;k<=n;k++) { scanf("%d %d",&x,&y); for(i=x;i<x+10;i++) { for(j=y;j<y+10;j++) { arr[i][j]=1; } } } for(i=1;i<=100;i++) { for(j=1;j<=100;j++) { if(arr[i][j]==1) { sum++; } } } printf("%d",sum); return 0; } */

/* #include <stdio.h> int main() { int m,n,sum=0,min=10000,i,j; scanf("%d %d",&m,&n); for(i=m; i<=n; i++) { for(j=1; j<=i; j++) { if(i%j==0&&i/j==j) { sum+=i; if(i<min) { min=i; } } } } printf("%d\n%d",sum,min); return 0; } int arr[50]; arr[0] ~ arr[49] int arr[3][5]; arr[0][0] ~ arr[2][4] #include <stdio.h> int main() { int i, j, n,k=1; int arr[101][101]={}; scanf("%d",&n); for(j=1;j<=n;j++) { for(i=1;i<=n;i++) { arr[i][j]=k++; } } 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,i,j,k=1; int arr[101][101]; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { arr[i][j]=k++; } } 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,i,j,k=1; int arr[101][101]={}; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=n;j>=1;j--) { arr[i][j]=k++; } } 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,i,j,k=1; int arr[101][101]={}; scanf("%d",&n); for(j=1;j<=n;j++) { for(i=1;i<=n;i++) { arr[i][j]=k++; } } 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,i,j,k=1; int arr[101][101]={}; scanf("%d",&n); for(j=1;j<=n;j++) { for(i=n;i>=1;i--) { arr[i][j]=k++; } } 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,m,i,j,k=1; int arr[101][101]={}; scanf("%d %d",&n,&m); for(i=n;i>=1;i--) { for(j=m;j>=1;j--) { arr[i][j]=k++; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,m,i,j,k=1; int arr[101][101]={}; scanf("%d %d",&n,&m); for(i=n;i>=1;i--) { for(j=1;j<=m;j++) { arr[i][j]=k++; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,m,i,j,k=1; int arr[101][101]; scanf("%d %d",&n,&m); for(j=m;j>=1;j--) { for(i=n;i>=1;i--) { arr[i][j]=k++; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,m,i,j,k=1; int arr[101][101]={}; scanf("%d %d",&n,&m); for(j=m;j>=1;j--) { for(i=1;i<=n;i++) { arr[i][j]=k++; } } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j,k=1; int arr[101][101]={}; scanf("%d",&n); for(i=1;i<=n;i++) { if(i%2==0) { for(j=n;j>=1;j--) { arr[i][j]=k++; } } else { for(j=1;j<=n;j++) { arr[i][j]=k++; } } } 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,i,j,k=1; int arr[101][101]; scanf("%d",&n); for(j=1;j<=n;j++) { if(j%2==0) { for(i=n;i>=1;i--) { arr[i][j]=k++; } } else { for(i=1;i<=n;i++) { arr[i][j]=k++; } } } 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,m,i,j,k=1; int arr[101][101]={}; scanf("%d %d",&n,&m); for(i=1; i<=n; i++) { if(i%2!=0) { for(j=m; j>=1; j--) { arr[i][j]=k++; } } else { for(j=1; j<=m; j++) { arr[i][j]=k++; } } } for(i=n;i>=1;i--) { for(j=1;j<=m;j++) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,m,i,j,k=1; int arr[101][101]={}; scanf("%d %d",&n,&m); for(j=1;j<=m;j++) { if(j%2!=0) { for(i=n;i>=1;i--) { arr[i][j]=k++; } } else { for(i=1;i<=n;i++) { arr[i][j]=k++; } } } for(i=1;i<=n;i++) { for(j=m;j>=1;j--) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; int arr[21][21]={}; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&arr[i][1]); } for(i=2;i<=n;i++) { for(j=2;j<=i;j++) { arr[i][j]=arr[i][j-1]-arr[i-1][j-1]; } } for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { printf("%d ",arr[i][j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int arr[12][11]= {}; int 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 fall\n",j); break; } else if(arr[i][j]>0) { printf("%d crash\n",j); break; } else if(i==1) { printf("%d safe\n",j); } } } } return 0; } */

/* #include <stdio.h> int main() { int n,k,i,max=0,sum=0; int arr[100000]; scanf("%d %d ",&n,&k); for(i=0; i<n; i++) { scanf("%d",&arr[i]); } for(i=0; i<k; i++) { max+=arr[i]; } sum=max; for(i=0; i<n-k; i++) { sum=sum-arr[i]+arr[i+k]; if(sum>max) { max=sum; } } printf("%d",max); return 0; } */ /* #include <stdio.h> int main() { int n,k=0,t=0,a=0,b=0,c=1000000,d=0,i,j; scanf("%d",&n); for(i=1; i<=n; i++) { if(n%i==0) { k=0; for(j=1; j<=n; j++) { if(i%j==0) { k++; } } if(k==2) { c=i; b=n/c; a=c; t=0; for(j=1; j<=b; j++) { if(b%j==0) { t++; } } if(t==2) { printf("%d %d",a,b); return 0; } } } } printf("wrong number"); return 0; } */ /* #include <stdio.h> int main() { int memo[24]= {}; int n,i,t; scanf("%d",&n); for(i=1; i<=n; i++) { scanf("%d",&t); memo[t]++; } for(i=1; i<=23; i++) { printf("%d ",memo[i]); } return 0; } */ /* #include <stdio.h> int main() { int n,i,t,a=23; int memo[24]={}; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&t); memo[t]++; } for(i=1;i<=n;i++) { if(memo[i]>0) { if(i<=a) { a=i; } printf("%d",a); return 0; } } } */ /* #include <stdio.h> int main() { int a,b,n,m,i; int memo[10001]={}; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a); memo[a]=1; } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d",&b); printf("%d ",memo[b]); } return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[91]={}; int a=0,i,t=0,memo[26]={}; gets(str); for(i=0;str[i]!=0;i++) { if(str[i]>='a'&&str[i]<='z') { t=str[i]-97; memo[t]++; } } for(i=0;i<26;i++) { printf("%c:%d\n",i+97,memo[i]); } return 0; } */ 멘탈바사삭

/* #include <stdio.h> int main() { int a,b=0,rev=0; scanf("%d",&a); while(a>0) { rev=rev*10+a%10; b=b+a%10; a=a/10; } printf("%d\n%d",rev,b); return 0; } */ /* #include <stdio.h> int main() { int m,n,k=0,a=0,b=0,i,j; scanf("%d %d",&m,&n); for(i=m; i<=n; i++) { k=0; for(j=1; j<=i; j++) { if(i%j==0) { k++; } } if(k==2) { b=b+i; } } if(b==0) { printf("-1"); } else { printf("%d\n%d",b,i); } return 0; } */ /* #include<stdio.h> #include<string.h> int main() { char str[49]; int i,a=0; scanf("%s",str); a=10; for(i=0;str[i]!=NULL;i++) { if(str[i]=='('&&str[i+1]=='(') { a=a+5; } else if(str[i]==')'&&str[i+1]=='(') { a=a+10; } else if(str[i]=='('&&str[i+1]==')') { a=a+10; } else if(str[i]==')'&&str[i+1]==')') { a=a+5; } } printf("%d",a); } int arr[50]; arr[0]~arr[49] char str[50]; str[0] ~ str[49] #include <stdio.h> #include <string.h> int main() { char str[50]; int i; //scanf("%s",str); gets(str); //printf("%s",str); for(i=0;str[i]!=NULL;i++) { printf("%c",str[i]); } printf(" %d",strlen(str)); //문자열 str의 길이 = strlen(str) return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[29]; gets(str); printf("%s",str); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[99]; int i; gets(str); for(i=0;str[i]!=NULL;i++) { if(str[i]!=' ') { printf("%c",str[i]); } } return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[99]; int a=0,b=0,i; scanf("%s",str); for(i=0;str[i]!=NULL;i++) { if(str[i]=='c'||str[i]=='C') { a++; } if((str[i]=='c'&&str[i+1]=='c')||(str[i]=='c'&&str[i+1]=='C')||(str[i]=='C'&&str[i+1]=='c')||(str[i]=='C'&&str[i+1]=='C')) { b++; } } printf("%d\n%d",a,b); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[99]; int a=0,i; gets(str); for(i=0;str[i]!=NULL;i++) { if(str[i]=='l'&&str[i+1]=='o'&&str[i+2]=='v'&&str[i+3]=='e') { a++; } } printf("%d",a); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str1[21],str2[21],str3[21]; scanf("%s %s %s",str1,str2,str3); if(str1[0]==str3[strlen(str3)-1] &&str2[0]==str1[strlen(str1)-1] &&str3[0]==str2[strlen(str2)-1]) { printf("good"); } else { printf("bad"); } return 0; } */ /* #include <stdio.h> int main() { char a; scanf("%c",&a); printf("%d",NULL); return 0; } #include <stdio.h> #include <string.h> int main() { char str[1001]; int i; scanf("%s",str); for(i=0;str[i]!=0;i++) { if(str[i]>='A'&&str[i]<='Z') { str[i]+=32; } else if(str[i]>='a'&&str[i]<='z') { str[i]-=32; } } printf("%s",str); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[21]={},str1[21]={},str2[21]={}; int i; scanf("%s",str); for(i=0;str[i]!=0;i++) { str1[i]=str[i]+2; str2[i]=(str[i]*7)%80+48; } printf("%s\n%s",str1,str2); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[501]; int a=0,i; scanf("%s",str); for(i=0;str[i]!=0;i++) { str[i]-=48; a+=str[i]; } if(a%3==0) { printf("1"); } else { printf("0"); } return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str1[101]={},str2[101]={}; int i; scanf("%s %s",str1,str2); if(strlen(str1)>strlen(str2)) { printf("%s %s",str2,str1); } else if(strlen(str1)<strlen(str2)) { printf("%s %s",str1,str2); } else { for(i=0;str1[i]!=0;i++) { if(str1[i]>str2[i]) { printf("%s %s",str2,str1); break; } else if(str1[i]<str2[i]) { printf("%s %s",str1,str2); break; } } } return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[201]; int i; gets(str); for(i=0;str[i]!=0;i++) { if(str[i]>='d'&&str[i]<='z') { str[i]-=3; } else if(str[i]>='a'&&str[i]<='c') { str[i]+=23; } } printf("%s",str); return 0; } */ /* #include <stdio.h> int main() { int m,n,k=0,a,b=0,i,j; scanf("%d %d",&m,&n); a=n; for(i=m; i<=n; i++) { k=0; for(j=1; j<=i; j++) { if(i%j==0) { k++; } } if(k==2) { b=b+i; if(a>i) { a=i; } } } if(b==0) { printf("-1"); } else { printf("%d\n%d",b,a); } return 0; } */

/* #include <stdio.h> int main() { int a,b=0,i; int arr[7]; scanf("%d",&a); for(i=7;i>0;i--) { arr[i]=a%10; a=a/10; if(arr[i]!=0) { printf("%d",arr[i]); } b=b+arr[i]; } printf("\n%d",b); return 0; } */ /* #include <stdio.h> int main() { int m,n,k=0,a=0,b=0,i,j; scanf("%d %d",&m,&n); for(i=n; i<=m; i++) { for(j=1; j<=i; j++) { if(i%j==0) { k++; if(k==2) { b=b+i; a++; } } } } if(a==1) { printf("%d\n%d",b,i); } else if(a==0) { printf("%d",-1); } return 0; } */ /* #include<stdio.h> #include<string.h> int main() { char str[49]; int i,a=0; scanf("%s",str); a=10; for(i=0;str[i]!=NULL;i++) { if(str[i]=='('&&str[i+1]=='(') { a=a+5; } else if(str[i]==')'&&str[i+1]=='(') { a=a+10; } else if(str[i]=='('&&str[i+1]==')') { a=a+10; } else if(str[i]==')'&&str[i+1]==')') { a=a+5; } } printf("%d",a); } */

/* #include <stdio.h> int map[26][26]={}; int n,cnt=0; int a[600]={}; void dfs(int x,int y) { if(x<1||y<1||x>n||y>n||map[x][y]!=1) return ; map[x][y]=0; a[cnt]++; dfs(x+1,y); dfs(x-1,y); dfs(x,y+1); dfs(x,y-1); } int main() { int i,j,temp; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%1d",&map[i][j]); } } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(map[i][j]==1) { cnt++; dfs(i,j); } } } printf("%d\n",cnt); for(i=1; i<cnt; i++) { for(j=1;j<=cnt-i;j++) { if (a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } for(i=1;i<=cnt;i++) { printf("%d\n",a[i]); } return 0; } */ /* #include <stdio.h> int map[101][101]={}; int m,n,k; void bfs(int x,int y) { if(x<1||y<1||x>100||y>100||map[x][y]!=0) return ; map[x][y]=0; dfs(x+1,y); dfs(x-1,y); dfs(x,y+1); dfs(x,y-1); } int main() { int i,j,temp; scanf("%d %d %d",&m,&n,&k); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(map[i][j]=1) { cnt++; dfs(i,j) } } } } */ #include <stdio.h> int main() { int arr[101][101]= {},i,j,n,a,b,k; scanf("%d",&n); for(k=1; k<=n; k++) { scanf("%d %d",&a,&b); for(i=a; i<a+10; i++) { for(j=b; j<=b+10; j++) { arr[i][j]==1 } } } if(arr[i][j]==) }

/* #include <stdio.h> int main() { int n,k=1,t=0,i,j; int a; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&a); if(a==1) { t=t+k; k++; } else { k=1; } } printf("%d",t); return 0; } */ /* #include <stdio.h> int main() { int n,a=0,k,i,j; scanf("%d %d",&n,&k); for(i=1; i<=n; i++) { if(n%i==0) { a++; //i가 a번째 약수 if(a==k) { printf("%d",i); return 0; } } } printf("0"); return 0; } */ /* #include <stdio.h> int main() { double s,e,t=0,k=0,p=0,i; for(i=0;i<5;i++) { scanf("%lf %lf",&s,&e); t=e-s; if(t>=1) { t=t-1; if(t>4) { t=4; } } else if(t<1) { t=0; } k=k+t; } p=k*10000; if(k>=15) { printf("%.0lf",p*0.95); } else if(k<=5) { printf("%.0lf",p*1.05); } else { printf("%d",(int)p); } return 0; } */ /* #include <stdio.h> int main() { int m,n,k=0,t=0,a=0,i,j; scanf("%d %d",&m,&n); for(i=m; i<=n; i++) { for(j=1; j<=i; j++) { if(i%j==0) { t++; a++; } } } if(t==2&&a==) { k=k+j; printf("%d",k); } else { printf("-1\n%d",a); } return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char a; scanf("%c",&a); printf("%c",a); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[8]; scanf("%s",str); printf("%s",str); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[10]; int i; scanf("%s",str); if(str[0]=='l'&&str[1]=='o'&&str[2]=='v'&&str[3]=='e'&&str[4]==NULL) { printf("I love you."); } return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[100000]; int a=0,b=0,i; scanf("%s",str); for(i=0;str[i]!=NULL;i++) { if(str[i]=='(') { a++; } else { b++; } } printf("%d %d",a,b); return 0; } */ /* #include <stdio.h> #include <string.h> int main() { char str[10]; int i; scanf("%s",str); for(i=0;str[i]!=NULL;i++) { if(str[i]=='t') { printf("%d ",i+1); } } return 0; } */

/* #include <stdio.h> int main() { int n,a=0,b=0,i,j; scanf("%d",&n); for(i=0; i<n; i++) { for(j=1; j<=i; j++) { a=a+j; } } printf("%d",a); return 0; } */ //배열 //array /* #include <stdio.h> int main() { int arr[8]; //arr[0] ~ arr[7] int i,n;// scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&arr[i]); } for(i=0; i<n; i++) { printf("%d ",arr[i]); } //printf("%d",arr); } */ /* #include <stdio.h> int main() { int arr[1000]; int n,i; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&arr[i]); } for(i=n-1;i>=0;i--) { printf("%d ",arr[i]); } return 0; } */ /* #include <stdio.h> int main() { int arr[1000]; int n,i,j; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&arr[i]); } for(i=0; i<n; i++) { for(j=i; j<n; j++) { printf("%d ",arr[j]); } for(j=0;j<i;j++) { printf("%d ",arr[j]); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int arr[10]; int k,i; for(i=0;i<10;i++) { scanf("%d",&arr[i]); } scanf("%d",&k); printf("%d",arr[k-1]); return 0; } */ /* #include <stdio.h> int main() { int arr[48]; int n,a=0,b=0,i; scanf("%d",&n); for(i=0;i<n-1;i++) { scanf("%d",&arr[i]); a=a+arr[i]; } for(i=1;i<=n;i++) { b=b+i; } printf("%d",b-a); return 0; } */ /* #include <stdio.h> int main() { int arr[1000]; int n,i,j; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&arr[i]); } for(i=0; i<n; i++) { printf("%d: ",i+1); for(j=0; j<n; j++) { if(i==j) { continue; } if(arr[i]>arr[j]) { printf("> "); } else if(arr[i]<arr[j]) { printf("< "); } else { printf("= "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i=0; int arr[32]={0}; scanf("%d",&n); if(n==0) { printf("0"); return 0; } while(n>0) { arr[i]=n%2; i++; n=n/2; } while(i>0) { i--; printf("%d",arr[i]); } return 0; } */

/* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=i;j++) { if(j<i) { printf(" "); } else { printf("**"); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1; i<=n/2+1; i++) { for(j=n/2; j>=1; j--) { if(i<=j) { printf(" "); } else { printf("*"); } } for(j=1;j<=i;j++) { printf("*"); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int h,k,i,j; char d; scanf("%d %d %c",&h,&k,&d); if(d=='L') { for(i=1; i<=h; i++) { for(j=1; j<=i+k-1; j++) { if(i<=j) { printf("*"); } else { printf(" "); } } printf("\n"); } } else if(d=='R') { for(i=h; i>=1; i--) { for(j=1; j<=i+k-1; j++) { if(i<=j) { printf("*"); } else { printf(" "); } } printf("\n"); } } return 0; } */ /* #include <stdio.h> int main() { int h,r,i,j,k; scanf("%d %d",&h,&r); for(i=1; i<=r; i++) { for(j=1; j<=h*2-1; j++) { for(k=1; k<=h; k++) { if(j==k) { printf("*"); } else if(j+k==h*2) { printf("*"); } else { printf(" "); } } printf("\n"); } } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1; i<=2*n; i++) { for(j=1; j<=2*n; j++) { if(j+i==n+1||i-n==j||j-n==i||j+i==3*n+1) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */

//#include <stdio.h> //int main() //{ // int k,i,sum=0; // for(i=0;i<2;i++) // { // scanf("%d",&k); // if(k%2==0) // { // sum+=k*5; // } // else // { // sum+=(k+1)/2; // } // } // printf("%d",sum); // return 0; //} //for(시작식;조건식;증감식) // { // // } /* #include <stdio.h> int main() { int n; scanf("%d",&n); while(n>0) { printf("%d\n",n); n--; } return 0; } */ /* #include <stdio.h> int main() { int n; scanf("%d",&n); while(n>=1) { printf("%d\n",n); n--; } return 0; } */ /* #include <stdio.h> int main() { int n; scanf("%d",&n); while(n>=1) { printf("%d\n",n-1); n--; } return 0; } */ /* #include <stdio.h> int main() { int n,c=0; scanf("%d",&n); while(n>0) { n=n/10; c++; } printf("%d",c); return 0; } */ /* #include <stdio.h> int main() { int i,j; for(i=1; i<=3; i++) { for(j=1; j<=10; j++) { printf("*"); } for(j=1;j<=3;j++) { printf("^"); } printf("\n"); } } */ /* #include <stdio.h> int main() { int i,j,n; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("*"); } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(j==1||j==n||i==1||i==n) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(j==1||j==n||i==1||i==n||i==j||(i+j-1)==n) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(j==1||j==n||i==1||i==n||j==i||(i+j-1)==n||j==(n+1)/2||i==(n+1)/2) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,k,i,j; scanf("%d %d",&n,&k); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(j==1||j==n||i==1||i==n||(i+j-1)%k==0) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(j<=i) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(j<=i) { printf("*"); } else { printf(" "); } } printf("\n"); } for(i=n-1;i>=1;i--) { for(j=1;j<=n;j++) { if(j<=i) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=n;i>=1;i--) { for(j=1;j<=n;j++) { if(i>=j) { printf("*"); } else { printf(" "); } } printf("\n"); } return 0; } */ /* #include <stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(j<i) { printf(" "); } else { printf("*"); } } printf("\n"); } return 0; } */

/* #include <stdio.h> int main() { int n,k,t=1,i; scanf("%d %d",&n,&k); for(i=1;i<=k;i++) { t=t*n; } printf("%d",t); } */ /* #include <stdio.h> int main() { int n,i,t=1; scanf("%d",&n); for(i=n;i>=1;i--) { t=t*i; } printf("%d",t); } */ /* #include <stdio.h> int main() { int k,h; long long int o,p; scanf("%d %d",&k,&h); if(k%2==0) { o=k*5; } else { o=k*0.5+0.5; } if(h%2==0) { p=h*5; } else { p=0.5*h+0.5; } printf("%lld",o+p); } */ /* #include <stdio.h> int main() { int a,b,c=0,d=0,i; scanf("%d %d",&a,&b); for(i=a;i<=b;i++) { if(i%2==0) { c=c-i; } else { d=d+i; } } printf("%d",c+d); } */ /* #include <stdio.h> int main() { int a,b,c=0,d=0,i; scanf("%d %d",&a,&b); for(i=a;i<=b;i++) { if(i%2==0) { c=c-i; printf("-%d",i); } else { d=d+i; printf("+%d",i); } } printf("=%d",c+d); } */

/* #include <stdio.h> int main() { int a,b,c,d; scanf("%d %d %d",&a,&b,&c); printf("%d %d",(a+(b+c)/60)%24,(b+c)%60); return 0; } */ /* #include <stdio.h> int main() { int i; for(i=1;i<=100;i++) { printf("%d ",i); } } */ /* #include <stdio.h> int main() { int i,n; scanf("%d",&n); for(i=1;i<=n;i++) { printf("%d ",i); } } */ /* #include <stdio.h> int main() { double a,b,i; scanf("%lf %lf",&a,&b); for(i=a;i<=b;i+=0.01) { printf("%.2lf ",i); } } */ /* #include <stdio.h> int main() { int a,b,i; scanf("%d %d",&a,&b); for(i=a; i<=b; i++) { if(i%2!=0) { printf("%d ",i); } } } */ /* #include <stdio.h> int main() { int n,i,a=0; scanf("%d",&n); for(i=1; i<=n; i++) { if(i%2==0) a=a+i; } printf("%d",a); } */ /* #include <stdio.h> int main() { int n,i,a,b=0; scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&a); b=b+a; } printf("%d",b); } */ /* #include <stdio.h> int main() { int n,i,a=0,c=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a); if(a%2==0) { c++; } } printf("%d",c); } */ /* #include <stdio.h> int main() { int n,i,a=0; scanf("%d",&n); for(i=1;i<=n;i+=10) { a++; } printf("%d",a); } */ /* #include <stdio.h> int main() { int a,d,n,t,i; scanf("%d %d %d",&a,&d,&n); for(i=1;i<=n;i++) { t=a+(n-1)*d; } printf("%d",t); } */ /* #include <stdio.h> int main() { long long int a,r,n,t=1,i; scanf("%lld %lld %lld",&a,&r,&n); for(i=1;i<=n-1;i++) { t=t*r; } printf("%lld",a*t); } */ /* #include <stdio.h> int main() { long long int a; int m,d,n,i; scanf("%lld %d %d %d",&a,&m,&d,&n); for(i=1;i<=n-1;i++) { a=a*m+d; } printf("%lld",a); } */ /* #include <stdio.h> int main() { int a,n,max=0,i; scanf("%d\n",&n); for(i=1;i<=n;i++) { scanf("%d",&a); if(max<a) { max=a; } } printf("%d",max); } */ /* #include <stdio.h> int main() { int n,i; scanf("%d",&n); for(i=1;i<=n;i++) { if(n%i==0) { printf("%d ",i); } } } */ /* #include <stdio.h> int main() { int n,i,c=0; scanf("%d",&n); for(i=1; i<=n; i++) { if(n%i==0) { c++; } } if(c==2) { printf("prime"); } else { printf("not prime"); } } */

/* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if(a%2==0) { printf("%d\n",a); } if(b%2==0) { printf("%d\n",b); } if(c%2==0) { printf("%d",c); } return 0; } */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if(a%2==0) { printf("even\n",a); } else if(a%2!=0) { printf("odd\n",a); } if(b%2==0) { printf("even\n",b); } else if(b%2!=0) { printf("odd\n",b); } if(c%2==0) { printf("even\n",c); } else if(c%2!=0) { printf("odd\n",c); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a<0) { printf("minus\n"); if(a%2==0) { printf("even"); } else { printf("odd"); } } else if(a>0) { printf("plus\n"); if(a%2==0) { printf("even"); } else { printf("odd"); } } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a<=100&&a>=90) { printf("A"); } else if(a>=70) { printf("B"); } else if(a>=40) { printf("C"); } else { printf("D"); } return 0; } */ /* #include <stdio.h> int main() { char a; scanf("%c",&a); if(a=='A') { printf("best!!!"); } else if(a=='B') { printf("good!!"); } else if(a=='C') { printf("run!"); } else if(a=='D') { printf("slowly~"); } else { printf("what?"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a==1||a==2||a==12) { printf("winter"); } else if(a==3||a==4||a==5) { printf("spring"); } else if(a==6||a==7||a==8) { printf("summer"); } else { printf("fall"); } return 0; } */ /* #include <stdio.h> int main() { int a,b; scanf("%d %d",&a,&b); if(a>b) { printf(">"); } else if(a<b) { printf("<"); } else if(a==b) { printf("="); } return 0; } */ /* #include <stdio.h> int main() { int a,b; scanf("%d %d",&a,&b); if(a>=b) { printf("%d",a-b); } else if(a<b) { printf("%d",b-a); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a%7==0) { printf("multiple"); } else { printf("not multiple"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if((a>=30&&a<=40)||(a>=60&&a<=70)) { printf("win"); } else { printf("lose"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if((a>=50&&a<=70)||a%6==0) { printf("win"); } else { printf("lose"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a==2||a==4||a==6) { printf("enjoy"); } else { printf("oh my god"); } return 0; } */ /* #include <stdio.h> int main() { int a,b; scanf("%d %d",&a,&b); if((a%2==0)&&(b%2==0)) { printf("짝수+짝수=짝수"); } else if((a%2!=0)&&(b%2==0)) { printf("홀수+짝수=홀수"); } else if((a%2==0)&&(b%2!=0)) { printf("짝수+홀수=홀수"); } else if((a%2!=0)&&(b%2!=0)) { printf("홀수+홀수=짝수"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(((a%4==0)&&(a%100!=0))||a%400==0) { printf("yes"); } else { printf("no"); } return 0; } */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if((b<=a&&a<=c)||(a>=c&&a<=b)) { printf("%d",a); } else if((a>=b&&b>=c)||(c>=b&&b>=a)) { printf("%d",b); } else if((a>=c&&b<=c)||(a<=c&&b>=c)) { printf("%d",c); } else return 0; } */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); printf("%d%d",a,b); if(c<10) { printf("%02d",c); } else { printf("%d",c); } return 0; } */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); printf("%d%02d%03d",a,b,c); 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 ",a); if(b<=c) { printf("%d %d",b,c); } else { printf("%d %d",c,b); } } else if(b<=a&&b<=c) { printf("%d ",b); if(a<=c) { printf("%d %d",a,c); } else { printf("%d %d",c,a); } } else { printf("%d ",c); if(b<=a) { printf("%d %d",b,a); } else { printf("%d %d",a,b); } } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a>0) { printf("양수"); } else if(a==0) { printf("0"); } else { printf("음수"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a>=90) { printf("A"); } else if(a>=80) { printf("B"); } else if(a>=70) { printf("C"); } else if(a>=60) { printf("D"); } else { printf("F"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(a<=10) { printf("정상"); } else if(a<=20) { printf("과체중"); } else { printf("비만"); } return 0; } */ /* 최댓값 #include <stdio.h> int main() { float a,b,c,d,e,f,g,h,i,j; scanf("%f %f",&a,&b); c=(a+b); d=(a-b); e=(b-a); f=(a*b); g=(a/b); h=(b/a); i=(a^b); j=(b^a); if(c>=d&&c>=e&&c>=f&&c>=g&&c>=h&&c>=i&&c>=j) { printf("%.6f",c); } else if(d>=c&&d>=e&&d>=f&&d>=g&&d>=h&&d>=i&&d>=j) { printf("%.6f",d); } else if(e>=c&&e>=d&&e>=f&&e>=g&&e>=h&&e>=i&&e>=j) { printf("%.6f",e); } else if(f>=c&&f>=d&&f>=e&&f>=g&&f>=h&&f>=i&&f>=j) { printf("%.6f",f); } else if(g>=c&&g>=d&&g>=e&&g>=f&&g>=h&&g>=i&&g>=j) { printf("%.6f",g); } else if(h>=c&&h>=d&&h>=e&&h>=f&&h>=g&&h>=i&&h>=j) { printf("%.6f",h); } else if(i>=c&&i>=d&&i>=e&&i>=f&&i>=g&&i>=h&&i>=j) { printf("%.6f",i); } else { printf("%.6f",j); } return 0; } */ /* #include <stdio.h> int main() { int a,b; scanf("%d %d",&a,&b); if((a%400==0)||((a%4==0)&&(a%100!=0))) { if(b<8) { if(b==2) { printf("29"); } else if(b%2==0) { printf("30"); } else { printf("31"); } } else { if(b%2==0) { printf("31"); } else { printf("30"); } } } else { if(b<8) { if(b==2) { printf("28"); } else if(b%2==0) { printf("30"); } else { printf("31"); } } else { if(b%2==0) { printf("31"); } else { printf("30"); } } } return 0; } */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if(a>(b-c)) { printf("do not advertise"); } else if(a<(b-c)) { printf("advertise"); } else { printf("does not matter"); } return 0; } */ /* #include <stdio.h> int main() { int a,b,c,d; scanf("%d %d %d %d",&a,&b,&c,&d); if(a+b+c+d==0) { printf("모"); } else if(a+b+c+d==1) { printf("도"); } else if(a+b+c+d==2) { printf("개"); } else if(a+b+c+d==3) { printf("걸"); } else { printf("윷"); } return 0; } */

/* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if(a+b>c) { if(a==b&&b==c&&a==c) { printf("정삼각형"); } else if(a==b||b==c||a==c) { printf("이등변삼각형"); } else if((a*a)+(b*b)==(c*c)) { printf("직각삼각형"); } else { printf("삼각형"); } } else { printf("삼각형아님"); } return 0; } */ /* 1163 1168 1180 1204 1222 1229 */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if((((a+b+c)%1000)/100)%2==0) { printf("대박"); } else { printf("그럭저럭"); } return 0; } */ /* #include <stdio.h> int main() { int a,b; scanf("%d %d",&a,&b); if(b==1||b==2) { printf("%d",2013-(1900+(a/10000))); } else if(b==3||b==4) { printf("%d",2013-(2000+(a/10000))); } return 0; } */ /* #include <stdio.h> int main() { int a,b; scanf("%d",&a); b=((a/10+(a%10)*10)*2); b=b%100; printf("%d\n",b); if(b<=50) { printf("GOOD"); } else { printf("OH MY GOD"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if((a/10)==1&&((a%10)==1||(a%10)==2||(a%10)==3)) { printf("%dth",a); } else if((a%10)==1) { printf("%dst",a); } else if((a%10)==2) { printf("%dnd",a); } else if((a%10)==3) { printf("%drd",a); } else { printf("%dth",a); } return 0; } */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if((90-a)%5==0) { if((c-b)==(90-a)/5) { printf("same"); } else if((c-b)<(90-a)/5) { printf("win"); } else { printf("lose"); } } else if((90-a)%5!=0) { if((c-b)==(95-a)/5) { printf("same"); } else if((c-b)<(95-a)/5) { printf("win"); } else { printf("lose"); } } } */ /* #include <stdio.h> int main() { double a,b,c,d; scanf("%lf %lf",&a,&b); if(a<150) { c=a-100; } else if(a<160) { c=(a-150)/2+50; } else { c=(a-100)*0.9; } d=((b-c)*100)/c; if(d<=10) { printf("정상"); } else if(d<=20) { printf("과체중"); } else { printf("비만"); } return 0; } */ /* #include <stdio.h> int main() { int a; scanf("%d",&a); if(2013-a<2000) { printf("%d %d",113-a,1); } else { printf("%d %d",13-a,3); } return 0; } */ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if(a>b&&a>c) { if(a<(b+c)) printf("yes"); else printf("no"); } else if(b>a&&b>c) { if(b<(a+c)) printf("yes"); else printf("no"); } else { if(c<(a+b)) printf("yes"); else printf("no"); } return 0; } */ /* #include <stdio.h> int main() { int a,b,y,m,d; scanf("%d-%d",&a,&b); b=b/1000000; y=a/10000; m=a%10000/100; d=a%100; if(b==1||b==2) y=y+1900; else y=y+2000; printf("%04d/%02d/%02d ",y,m,d); if(b==1 || b==3) printf("M"); else printf("F"); return 0; } */