/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*/ /* 1536 #include <stdio.h> int n; long long int d[110]; long long int f(void) { long long int k=d[1]; for(int i=2;i<=n;i++){ if(k>d[i]){ k=d[i]; } } return k; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%lld", &d[i]); printf("%lld", f()); return 0; }*/ /* 1581 포인터 시작 #include <stdio.h> void myswap(int* pa,int* pb) { int sum=*pa+*pb; if(*pa>*pb){ *pa=*pb; *pb=sum-*pa; } } main() { int a, b; scanf("%d%d", &a, &b); myswap(&a, &b); printf("%d %d", a, b); } */ /* 서브 스트링 1610 포인터 문자 배열 #include<stdio.h> char s[101]; char* f(int a,int b) { char* ps=s; *(ps+a+b)= NULL; return ps+a; } int main(){ scanf("%s",s); int a,b; scanf("%d %d",&a,&b); printf("%s",f(a,b)); }*/ /* #include<stdio.h> int main(){ char a; scanf("%c",&a); printf("%c",a); } */ /* #include<stdio.h> int main(){ char s[10]; scanf("%s",s); printf("%s",s); } */ /* #include<stdio.h> int main(){ char s[40]; gets(s); printf("%s",s); } */ /* #include<stdio.h> #include<string.h> int main(){ char a[1200]; int i; scanf("%s",a); for(i=0;i<strlen(a);i++) { if((a[i]>=97)&&(a[i]<=122)) { a[i]-=32; } else if((a[i]>=65)&&(a[i]<=90)) { a[i]+=32; } else { } } printf("%s",a); } */ /* #include<stdio.h> int main(){ char a[20]; scanf("%s",a); if((a[0]=='l')&&(a[1]=='o')&&(a[2]=='v')&&(a[3]=='e')&&(a[4]==0)){ printf("I love you."); } }*/ /* #include<stdio.h> #include<string.h> int main(){ char s[200]; gets(s); for(int i=0;i<strlen(s);i++){ if(s[i]!=' '){ printf("%c",s[i]); } } }*/ /* 암호 처리 쓰레기 값이 있을 수도 있으니까 초기화를 시킴 #include<stdio.h> #include<string.h> int main(){ char s[21]={},v[21]={},l[21]={}; int i; scanf("%s",s); for(i=0;i<strlen(s);i++){ v[i]=s[i]+2; l[i]=(s[i]*7)%80+48; } v[i]=l[i]=0; printf("%s\n%s",v,l); return 0; }*/ /* 괄호 세기 #include<stdio.h> #include<string.h> int main(){ char s[100001]; scanf("%s",s); int a=0,b=0; for(int i=0;i<strlen(s);i++){ if(s[i]==')'){ a+=1; } else if(s[i]=='('){ b+=1; } } printf("%d %d",b,a); }*/ /* 1414 c언어를 찾아라 #include<stdio.h> #include<string.h> int main(){ char s[101]={}; int a=0,b=0; scanf("%s",s); for(int i=0;i<strlen(s);i++){ if((s[i]=='C')||(s[i]=='c')) { a+=1; if((s[i+1]=='C')||(s[i+1]=='c')) { b+=1; } } } printf("%d\n%d",a,b); } */ /* 1418 #include<stdio.h> #include<string.h> int main(){ char s[12]={}; scanf("%s",s); for(int i=0;i<strlen(s);i++) { if(s[i]=='t'){ printf("%d ",i+1); } } }*/ /* 1419 #include<stdio.h> #include<string.h> int main(){ char s[101]={}; int a=0; gets(s); for(int i=0;i<=strlen(s)-3;i++){ if(s[i]=='l'&& s[i+1]=='o'&& s[i+2]=='v'&& s[i+3]=='e') { a++; } } printf("%d",a); }*/ /* 1733 #include<stdio.h> #include<string.h> int main(){ char s[1000]={}; scanf("%s",s); if(s[0]=='I'&& s[1]=='O'&& s[2]=='I'&& s[3]==0 ){ printf("IOI is the International Olympiad in Informatics."); } else{ printf("I don't care."); } }*/ /* 1734 #include<stdio.h> int main(){ char s[13]={}; scanf("%s",s); printf("welcome! %s",s); }*/ /*1754 #include<stdio.h> #include<string.h> int main(){ char a[1000]={},b[1000]={}; scanf("%s %s",a,b); if(strlen(a)>strlen(b)) { printf("%s %s",b,a); } else if(strlen(a)<strlen(b)) { printf("%s %s",a,b); } else { for(int i=0;i<strlen(a);i++){ if(a[i]>b[i]){ printf("%s %s",b,a); break; } else if(a[i]<b[i]) { printf("%s %s",a,b); break; } } } }*/ // 1990 /* #include<stdio.h> #include<string.h> int main(){ char s[500]={}; int sum=0; int len; scanf("%s",s); //len=strlen(s); //for(int i=0;i<len;i++){ for(int i=0;s[i]!=0;i++) { sum+=s[i]-48; } if(sum%3==0){ printf("1"); } else{ printf("0"); } } */ /* 2721 #include<stdio.h> #include<string.h> int main(){ char a[20]={},b[20]={},c[20]={}; scanf("%s %s %s",a,b,c); if(a[strlen(a)-1]==b[0]&& b[strlen(b)-1]==c[0]&& c[strlen(c)-1]==a[0] ){ printf("good"); } else{ printf("bad"); } }*/ /* 구조체 .. #include<stdio.h> struct sch { char name[10]; int y,m,d; }; int main(){ struct sch a[100]; //a.y=2014; //scanf("%d",&a.y); for( int i=0;i<100;i++) { scanf("%s %d %d %d",a[i].name,&a[i].y,&a[i].m) } } */ /* 구조체 석차 계산 #include<stdio.h> struct student { int j,s; }; int main(){ int n,tmp; struct student st[200]; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&st[i].j); } for(int i=0;i<n;i++){ tmp=1; for(int j=0;j<n;j++){ if(st[i].j<st[j].j){ tmp++; } } st[i].s=tmp; } for(int i=0;i<n;i++){ printf("%d %d\n",st[i].j,st[i].s); } }*/

/* 1551 #include <stdio.h> int n, d[100010], k; int f(int k) { for(int i=1;i<=n;i++){ if(d[i]==k){ return i; } } return -1; } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &d[i]); scanf("%d", &k); printf("%d\n", f(k)); }*/ /* 1555 #include <stdio.h> int n; long long int f(int n) { long long int sum=0; for(long long int i=1;i<=n;i++){ sum+=i; } return sum; } int main() { scanf("%d", &n); printf("%lld\n", f(n)); } */ /* 1620 자릿수의 합 변수형 지정 잘해주자 #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) { long long int c=a/gcd(a,b); long long int d=b/gcd(a,b); return gcd(a,b)*c*d; } int main() { int a, b; scanf("%d%d", &a, &b); printf("%lld\n", lcm(a, b)); //printf("%d",gcd(a,b)); } */ /* 자릿수의 합 #include<stdio.h> long long int n; int f(long long int n) { int sum=0; while(n>0){ sum+=n%10; n=n/10; } if(sum/10!=0){ int d=sum%10+sum/10; if(d/10!=0){ int c=d%10+d/10; return c; } return d; } else{ return sum; } } int main(){ scanf("%lld",&n); printf("%d",f(n)); } */

/* 약수 개수 구하는 함수 int f(int n) { int c=0; for(int i=1; i<=n;i++) { if(n%i==0){ c++; } } return c; } */ /* 정수 뒤집어 리턴하기 long long int f(long long int n) { long long int k=0; while(n!=0){ k=k*10+n%10; n=n/10; } return k; }*/ /* 최대공약수 리턴하기 int gcd(int a,int b) { int r=a%b; while(r!=0){ a=b; b=r; r=a%b; } return b; }*/ /* 배열의 최대값 위치 리턴하기 int maxi(int a,int b) { int c=a; //c== 최댓값의 위치 for(int i=a;i<=b;i++){ if(d[c]<d[i]){ c=i; } } return c; }*/ /* 어떤 값보다 크거나 같은 값이 처음 나타나는 위치를 출력하시오. int lower_bound(int k) { for(int i=1;i<=n;i++){ if(d[i]>=k){ return i; } } return n+1; }*/ /* 어떤 값보다 큰 값이 처음 나타나는 위치를 출력하시오. int upper_bound(int k) { for(int i=1;i<=n;i++){ if(d[i]>k){ return i; } } return n+1; }*/ /* 절대값 함수 #include<stdio.h> float d(float n) { if(n<0){ n=n*(-1); } return n; } int main(){ float n; scanf("%f",&n); printf("%.7g",d(n)); }*/ /* 가장 큰 값 위치 리턴하기 int f() { int c=0; for(int i=0;i<n;i++){ if(d[i]>d[c]){ c=i; } } return c+1; }*/ /* 받는 값 출력 값 형을 맞추어 주자 int*int는 int범위 내에서 같은 형끼리 비교 연산 해야함 int sqrt(long long int n) { if(n==0){ return 0; } for(int i=1;;i++){ if(n<(long long int)i*i){ return i-1; } } }*/ /* 만약 1 2147483647 처럼 입력이 들어올 경우를 생각한다면 그치 long long int pow(int a, int n) { if(n==0){ return 1; } if(a==1){ return 1; } long long int b=(long long int)a; for(int i=1;i<=n-1;i++){ b*=a; } return b; }*/ /* self number 개 어려움// int d(int a) 각 자릿수+본래 값 이 함수를 잘 정의하자 #include<stdio.h> int memo[5001]={}; int d(int a) { int sum=a; while(a>0) { sum+=a%10; a=a/10; } return sum; } void self(int i) { memo[d(i)]=1; } int main(){ int a,b,i,sum=0; scanf("%d %d",&a,&b); for(int i=1;i<=5001;i++) { self(i); } for(i=a;i<=b;i++) { if(memo[i]==0) { sum+=i; } } printf("%d",sum); } */

/* #include<stdio.h> int main(){ int a[101][101]; int h,w,n,l[100],d[100],x[100],y[100]; scanf("%d %d",&h,&w); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d %d %d %d",&l[i],&d[i],&x[i],&y[i]); } int k[100][100]={}; for(int i=1;i<=n;i++){ if(d[i]==0){ for(int j=1;j<=l[i];j++){ k[x[i]][y[i]+j-1]=1; } } else{ for(int j=1;j<=l[i];j++){ k[x[i]-1+j][y[i]]=1; } } } for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ printf("%d ",k[i][j]); } printf("\n"); } }*/ #include<stdio.h> int main(){ int a[101][101]={}; int n; scanf("%d",&n); int e=1; int s=1; for(int i=n;i>=1;i--){ if(s==1){ int x=n; for(int j=n-i+1;j<=n;j++){ a[x--][j]=e++; } s=-1; } else{ int x=n-i+1; for(int j=n;j>=n-i+1;j--){ a[x++][j]=e++; } s=1; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ printf("%d ",a[i][j]); } printf("\n"); } }

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*/ /* 진격 후 결과 *주의점 else if 라는 것은 위에 것 모두 제치고 나서 실행하는 것 #include <stdio.h> int main(){ int a[12][11]={},i,j,k=0; for(i=1;i<=11;i++){ for(j=1;j<=10;j++){ scanf("%d",&a[i][j]); } } for(j=1;j<=10;j++){ if(a[11][j]!=0){ for(i=10;i>=1;i--){ if(a[i][j]>0){ printf("%d crash\n",j); break; } else if(a[i][j]<0){ printf("%d fall\n",j); break; } else if(i==1){ printf("%d safe\n",j); } } } } return 0; }*/ /* 지뢰 찾기 #include <stdio.h> int main(){ int a[11][11]={},n,i,j,k=0,c,d; for(i=1;i<=9;i++){ for(j=1;j<=9;j++){ scanf("%d",&a[i][j]); } } scanf("%d %d",&c,&d); if(a[c][d]==1){ printf("-1"); } else{ for(i=c-1;i<=c+1;i++){ for(j=d-1;j<=d+1;j++){ if(a[i][j]==1){ k++; } } } printf("%d",k); } } */ /* 그 생명 뭐시기 1 #include<stdio.h> int main() { int a[27][27]= {},i,j,k,l,c=0; int r[27][27]= {}; for(i=1; i<=25; i++) { for(j=1; j<=25; j++) { scanf("%d",&a[i][j]); } } for(i=1; i<=25; i++) { for(j=1; j<=25; j++) { c=0; for(k=i-1; k<=i+1; k++) { for(l=j-1; l<=j+1; l++) { if(a[k][l]==1) { c++; } } } if(a[i][j]==0) { if(c==3) { r[i][j]=1; } } else { c--; if(c==2 || c==3) { r[i][j]=1; } } } } for(i=1; i<=25; i++) { for(j=1; j<=25; j++) { printf("%d ",r[i][j]); } printf("\n"); } }*/ /* 2진수 변환 문제 #include<stdio.h> int main(){ int a[300],n,i,j=0; scanf("%d",&n); for(i=0;;i++){ a[i]=n%2; n=n/2; if(n==0){ j=i; break; } } for(i=j;i>=0;i--){ printf("%d",a[i]); } }*/ /* 개미 길찾기 #include<stdio.h> int main() { int a[12][12],r[12][12],i,j,k; for(i=1; i<=10; i++) { for(j=1; j<=10; j++) { scanf("%d",&a[i][j]); } } i=2; j=2; for(;;) { if(a[i][j]==2) { a[i][j]=9; break; } else if(a[i][j]==0) { a[i][j]=9; if(a[i][j+1]!=1) j++; else if(a[i+1][j]!=1) i++; else {break;} } } for(i=1; i<=10; i++){ for(j=1; j<=10; j++) { printf("%d ",a[i][j]); } printf("\n"); } }*/ #include<stdio.h> int main(){ int a[12][12],i,j,n,b[9][3]; for(i=1;1<=10;i++){ for(j=1;j<=10;j++){ scanf("%d",&a[i][j]); } } scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d %d",&b[i][1],&b[i][2]); } }

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*/ /*4개의 직사각형 넓이 #include <stdio.h> int main(){ int x1,y1,x2,y2,i,j,k,z=0; int a[101][101]={}; for(i=0;i<4;i++){ scanf("%d %d %d %d",&x1,&y1,&x2,&y2); for(j=x1;j<x2;j++){ for(k=y1;k<y2;k++){ a[j][k]=1; } } } for(i=0;i<101;i++){ for(j=0;j<101;j++){ if(a[i][j]==1){ z++; } } } printf("%d",z); }*/ /* 나도 IQ 150(입력이 안된 배열 출력하면 오류 생겨) #include <stdio.h> int main(){ int a[21][21],n,i,j; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i][1]); } for(i=2;i<=n;i++){ for(j=2;j<=i;j++){ a[i][j]=a[i][j-1]-a[i-1][j-1]; } } for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ printf("%d ",a[i][j]); } printf("\n"); } }*/ /* 왜 틀린 코드인지 10 crash 나옴 #include <stdio.h> int main(){ int a[12][11]={},i,j,k=0; for(i=1;i<=11;i++){ for(j=1;j<=10;j++){ scanf("%d",&a[i][j]); } } for(j=1;j<=10;j++){ if(a[11][j]!=0){ for(i=1;i<=10;i++){ if(a[i][j]>0){ k=1; } else if(a[i][j]<0){ k=2; } } if(k==1){ printf("%d crash\n",j); } else if(k==2){ printf("%d fall\n",j); } else { printf("%d safe\n",j); } } } return 0; }*/ #include<stdio.h> int main(){ int a[101][101]={}; int n; scanf("%d",&n); int }

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*/ /* #include <stdio.h> int main(){ int a,i,j; scanf("%d",&a); for(i=0;i<a;i++){ for(j=a-i;j>0;j--){ printf("*"); } printf("\n"); } }*/ /* #include <stdio.h> int main(){ int a,i,j; scanf("%d",&a); for(i=0;i<(a+1)/2;i++){ for(j=0;j<((a+1)/2)-1-i;j++){ printf(" "); } for(j=a;j>=a-2*i;j--){ printf("*"); } printf("\n"); } }*/ /* 배열 array int arr[101]; arr[0] arr[1] arr[2] .... arr[100] int s[6]; int i; s[0]= s[1]= s[2]= s[3]= s[4]= s[5]= n개 0 ~ n-1 1 ~ n for(i=0;i<6;i++) { scanf("%d",&s[i]); } scanf("%d,&n); int arr[n]; int arr[100]; int k, i; scanf("%d",&k); for(i=0;i<k;i++) { } */ /* #include<stdio.h> int main(){ int a[1000]; int n,i; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&a[i]); } for(i=0;i<n;i++){ printf("%d ",a[n-1-i]); } } */ /* #include<stdio.h> int main(){ int a[100]; int k,i; scanf("%d",&k); for(i=0;i<k;i++){ scanf("%d",&a[i]); } for(i=0;i<k;i++){ printf("%d\n",a[i]); } for(i=0;i<k;i++){ printf("%d\n",a[i]); } }*/ /* #include<stdio.h> int main(){ int a[11]; int k,i; for(i=1;i<=10;i++){ scanf("%d",&a[i]); } scanf("%d",&k); printf("%d",a[k]); }*/ /* #include<stdio.h> int main(){ int a[50],i,n,sum=0; scanf("%d",&n); for(i=0;i<n-1;i++){ scanf("%d",&a[i]); } for(i=0;i<n-1;i++){ sum=sum+a[i]; } printf("%d",((n*(n+1))/2)-sum); }*/ /* #include <stdio.h> int main() { int a[1000]; int n,i,j; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&a[i]); } for(i=0; i<n; i++) { printf("%d: ",i+1); for(j=0; j<n; j++) { if(i!=j) { if(a[i]<a[j]) { printf("< "); } else if(a[i]>a[j]) { printf("> "); } else { printf("= "); } } } printf("\n"); } } */ /* #include<stdio.h> int main(){ int a[101][101],n,i,j,k=1; scanf("%d",&n); for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ a[i][j]=k++; } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d ",a[i][j]); } printf("\n"); } } */ /* #include<stdio.h> int main(){ int a[101][101],n,i,j,k=1; scanf("%d",&n); for(j=1;j<=n;j++){ for(i=1;i<=n;i++){ a[i][j]=k++; } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d ",a[i][j]); } printf("\n"); } }*/ /* #include<stdio.h> int main(){ int a[101][101],n,k,i,j; scanf("%d %d",&n,&k); int o=n*k; for(i=1;i<=n;i++){ for(j=1;j<=k;j++){ a[i][j]=o--; } } for(i=1;i<=n;i++){ for(j=1;j<=k;j++){ printf("%d ",a[i][j]); } printf("\n"); } }*/ /* #include<stdio.h> int main(){ int a[101][101],n,m,i,j; scanf("%d %d",&n,&m); int o=n*m; for(j=1;j<=m;j++){ for(i=1;i<=n;i++){ a[i][j]=o--; } } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ printf("%d ",a[i][j]); } printf("\n"); } }*/ /* #include<stdio.h> int main(){ int a[101][101],n,i,j,k=1; scanf("%d",&n); for(i=1;i<=n;i++){ if(i%2!=0){ for(j=1;j<=n;j++){ a[i][j]=k++; } } else{ for(j=n;j>=1;j--){ a[i][j]=k++; } } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d ",a[i][j]); } printf("\n"); } }*/ /* #include<stdio.h> int main(){ int a[101][101],n,i,j,k=1; scanf("%d",&n); for(j=1;j<=n;j++){ if(j%2!=0){ for(i=1;i<=n;i++){ a[i][j]=k++; } } else{ for(i=n;i>=1;i--){ a[i][j]=k++; } } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ printf("%d ",a[i][j]); } printf("\n"); } }*/ /* 어려워요 #include<stdio.h> int main(){ int a[101][101]={0},n,k,x,y,i,j,sum,c=0; scanf("%d",&n); for(k=1;k<=n;k++){ scanf("%d %d",&x,&y); for(i=y;i<y+10;i++){ for(j=x;j<x+10;j++){ a[i][j]=1; } } } for(i=1;i<=100;i++){ for(j=1;j<=100;j++){ if(a[i][j]==1){ c++; } } } printf("%d",c); }*/

/*삼각형 1 #include<stdio.h> int main(){ int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(j<=i){ printf("*"); } else{ printf(" "); } } printf("\n"); } return 0; }*/ /*삼각형 3 #include <stdio.h> int main(){ int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i<=j){ printf("*"); } else{ printf(" "); } } printf("\n"); } return 0; }*/ /*삼각형 4 #include <stdio.h> int main(){ int n,i,j,k; scanf("%d",&n); for(i=0;i<(2*n)-1;i++){ for(j=0;j<n;j++){ if(i<n){ if(j<=i){ printf("*"); } } else if(i>=n){ if((-i+2*n-2)>=j){ printf("*"); } } else{ printf(" "); } } printf("\n"); } }*/ /*삼각형 4 #include<stdio.h> int main() { int i, j, n; scanf("%d", &n); for(i = 1; i <= n; i++) { for(j = 1; j <= i; j++) { printf("*"); } printf("\n"); } for(i = n - 1; i >= 1; i--) { for(j = 1; j <= i; j++) { printf("*"); } printf("\n"); } return 0; }*/

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*/ /* 아 진짜 에바 //ex) 1 2 3 4 6 12 #include <stdio.h> int main(){ int n,i,k,cnt=0,dk,t,c=0; scanf("%d",&n); for(i=2;i<n;i++){ if(n%i==0){//i가 n의 약수일때 //n의 약수인 i가 소수인지 판별 ex)21라면 i가 3 7 cnt=0; for(k=2;k<i;k++){ if(i%k==0){ cnt++; } } if(cnt==0) { dk=n/i; for(t=2;t<dk;t++){ if(dk%t==0){ c++; } } if(c==0){ printf("%d ",i); } else{ printf("wrong number"); } } } } if(n==1||n==2) printf("wrong number"); }*/ /* #include <stdio.h> int main(){ int i,j,k; for(i=0;i<5;i++) { for(j=0;j<3;j++) { printf("*"); } for(j=0;j<5;j++) { printf("!"); } printf("\n"); } return 0; } */ //사각형출력하기 1-4 +빗금사각형 //삼각형출력하기 1-5 + 평행사변형 1,2 /*사각형 1 #include <stdio.h> int main(){ int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ printf("*"); } printf("\n"); } }*/ /*2 #include<stdio.h> int main() { int n,i,j; scanf("%d",&n); for(i=0; i<n; i++) { for(j=0; j<n; j++) { if(i==0||i==n-1||j==0||j==n-1) { printf("*"); } else { printf(" "); } } printf("\n"); } }*/ /*3 #include <stdio.h> int main(){ int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i==0||i==n-1||j==0||j==n-1||i==j||i+j==n-1) { printf("*"); } else{ printf(" "); } } printf("\n"); } }*/ /*4 #include <stdio.h> int main(){ int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i==0||i==n-1||j==0||j==n-1||i==j||i+j==n-1||j==(n)/2||i==(n)/2){ printf("*"); } else{ printf(" "); } } printf("\n"); } }*/ /*빗금친 사각형 출력 #include <stdio.h> int main(){ int n,k,i,j; scanf("%d %d",&n,&k); for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(i==0||i==n-1||j==0||j==n-1||(i+j+1)%k==0){ printf("*"); } else{ printf(" "); } } printf("\n"); } }*/ /* #include <stdio.h> int main(){ int n,i,j; scanf("%d",&n); for(i=0;i<n;i++){ for(j=0;j<=i;j++){ printf("*"); } printf("\n"); } }*/

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*/ /* 소수 구하기 #include <stdio.h> int main(){ int a,i; scanf("%d",&a); for(i=2;i<=a;i++){ if(a%i==0){ if(a!=i){ printf("not prime"); break; } else if(a==i){ printf("prime"); } } } }*/ /*약수 구하기 #include <stdio.h> int main(){ int n,i; scanf("%d",&n); for(i=1;i<=n;i++){ if(n%i==0){ printf("%d ",i); } } }*/ /*1의 개수 구하기 #include <stdio.h> int main(){ int n,i,k=0; scanf("%d",&n); for(i=1;i<=n;i++){ if(i%10==1){ k+=1; } } printf("%d",k); }*/ /* 수열의 값 구하기 #include <stdio.h> int main(){ int a,b,c,n,i=1,k=0; scanf("%d %d %d %d",&a,&b,&c,&n); while(i<=n){ if(i==1){ k=a; } else{ k=k*(b)+c; } i++; } printf("%d",k); }*/ /* #include <stdio.h> int main(){ int n,i,k; scanf("%d",&n); for(i=2;i<n;i++){ if(n%i==0){ for(k=2;k<=i;k++){ if(i%k==0){ if(i!=k){ printf("wrong number"); break; } else if(i==k){ printf("%d ",i); } } } } } return 0; }*/

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*/ /* #include <stdio.h> int main(){ int a,b,i,sum=0; scanf("%d %d",&a,&b); for(i=a;i<=b;i++){ if(i%2==0){ sum-=i; printf("-%d",i); } else{ sum+=i; printf("+%d",i); } } printf("=%d",sum); }*/ /* #include<stdio.h> int main() { int a,b,i,k=0,t=0; scanf("%d %d",&a,&b); for(i=a; i<=b; i++) { if(i%2==0) { k-=i; printf("-%d",i); } else { t+=i; if(t==a) { printf("%d",i); } else { printf("+%d",i); } } } printf("=%d",k+t); }*/ /* #include<stdio.h> int main(){ int a; scanf("%d",&a); if(a%7==0){ printf("multiple"); } else{ printf("not multiple"); } }*/ /* #include <stdio.h> int main(){ int a; scanf("%d",&a); switch(a){ case 1: case 2: case 12: printf("winter"); break; case 3: case 4: case 5: printf("spring"); break; case 6: case 7: case 8: printf("summer"); break; case 9: case 10: case 11: printf("fall"); break; } }*/ /* #include<stdio.h> int main() { int a; scanf("%d",&a); switch(a/10) { case 10: case 9: printf("A"); break; case 8: printf("B"); break; case 7: printf("C"); break; case 6: printf("D"); break; default: printf("F"); } return 0; }*/ /* #include <stdio.h> int main(){ int a; scanf("%d",&a); switch(a){ case 1: case 3: case 5: case 7: printf("oh my god"); break; case 2: case 4: case 6: printf("enjoy"); break; } return 0; } #include <stdio.h> int main(){ //1부터 n까지 출력하기 int i,n,k; scanf("%d",&n); for(i=1; i<=n;i++) { printf("%d ",i); } printf("\n"); i=1; while(i<=n) { printf("%d ",i); i++; } printf("\n"); //n부터 1까지 출력 while(n>0) { printf("%d ",n); n--; } printf("n부터 1까지 출력\n"); n=5; do { printf("%d ",n); n--; }while(n>0); printf("n부터 1까지 출력\n"); } */ /* #include<stdio.h> int main(){ int a,i; scanf("%d",&a); i=0; while(i<=a){ printf("%d\n",i); i++; } }*/ /* #include <stdio.h> int main(){ int a,i,sum=0; scanf("%d",&a); i=1; while(i<=a){ if(i%2==0){ sum+=i; } i++; } printf("%d",sum); return 0; }*/ /* #include<stdio.h> int main(){ long long int a,b,c,i,k; scanf("%lld %lld %lld",&a,&b,&c); i=1; k=a; while(i<c){ k=k*b; i++; } printf("%lld",k); }*/ /* #include<stdio.h> int main(){ long long int a,b,c,d,i,k; scanf("%lld %lld %lld %lld",&a,&b,&c,&d); i=1; k=a; while(i<d){ k=k*b+c; i++; } printf("%lld",k); }*/ /* #include<stdio.h> int main(){ int n; scanf("%d",&n); do{ printf("%d\n",n-1); n--; }while(n!=0); }*/ /* #include<stdio.h> int main(){ int a,i; scanf("%d",&a); for(i=a-1;i>=0;i--){ printf("%d\n",i); } }*/ /* #include<stdio.h> int main(){ int n,c=0; scanf("%d",&n); while(n>0){ n=n/10; c=c+1; } printf("%d",c); }*/ /* #include <stdio.h> int main(){ int n,i=1,x=1; scanf("%d",&n); while(i<=n){ x=x*i; i++; } printf("%d",x); }*/ /* #include<stdio.h> int main(){ int n,k,i=1,x; scanf("%d %d",&n,&k); x=n; if(k==0){ printf("1"); } else{ while(i<k){ x=x*n; i++; } printf("%d",x); } }*/

/*#include <stdio.h> #include <stdlib.h> int main()++ { printf("Hello world!\n"); return 0; }*/ /* #include <stdio.h> int main(){ int i; for(i=1; i<=100; i++) { printf("%d ", i); } }*/ /* #include <stdio.h> int main(){ int n,i; scanf("%d",&n); for(i=1;i<=n;i++){ printf("%d ",i); } return 0; }*/ /* #include <stdio.h> int main() { int a,b,i; scanf("%d %d",&a,&b); if(a<b) { for(i=a; i<=b; i++) { printf("%d ",i); } } else { for(i=b; i<=a; i++){ printf("%d ",i); } } return 0; }*/ /* #include <stdio.h> int main(){ char a,b,i; scanf("%c %c",&a,&b); for(i=a;i<=b;i++){ printf("%c ",i); } return 0; }*/ /* #include <stdio.h> int main(){ double a,b,i; scanf("%lf %lf",&a,&b); for(i=a;i<=b;i+=0.01){ printf("%0.2lf ",i); } }*/ /* #include <stdio.h> int main(){ int a,i; scanf("%d",&a); for(i=1;i<=a;i++){ printf("*"); } return 0; }*/ /* #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; scanf("%d",&n); printf("%d",(n*(n+1))/2); }*/ /* #include <stdio.h> int main(){ int a,i, s=0; scanf("%d",&a); for(i=1;i<=a;i++){ s += i; } printf("%d", s); }*/ /* #include <stdio.h> int main(){ int a,i,s=0; scanf("%d",&a); for(i=1;i<=a;i++){ if(i%2==0){ s+=i; } } printf("%d",s); }*/ /* #include <stdio.h> int main(){ int a,b,c,s=0; scanf("%d %d",&a,&b); for(c=a;c<=b;c++){ if(c%3==0){ s+=c; } } printf("%d",s); }*/ /* #include<stdio.h> int main() { int n, i, k; scanf("%d", &n); for(i=0; i<n; i++) { scanf("%d", &k); } } }*/ /* #include <stdio.h> int main(){ int a,b,c,s=0; scanf("%d",&a); for(b=0;b<a;b++){ scanf("%d",&c); s+=c; } printf("%d",s); }*/ /* #include <stdio.h> int main(){ int a,b,c,s=0; scanf("%d",&a); for(b=0;b<a;b++){ scanf("%d",&c); if(c%5==0){ s+=c; } } printf("%d",s); }*/ /* #include <stdio.h> int main(){ int a,b,c,s=0; scanf("%d",&a); for(b=0;b<a;b++){ scanf("%d",&c); if(c%2==0){ s+=1; } } printf("%d",s); }*/ /* #include<stdio.h> int main() { int a,b,c,d=0; scanf("%d",&a); for(b=0;b<a;b++){ scanf("%d",&c); if(d<c){ d=c; } } printf("%d",d); }*/ /* #include <stdio.h> int main(){ int a,b,c=-1000000,d=1000000; for(b=0;b<5;b++){ scanf("%d",&a); if(c<a){ c=a; } if(d>a){ d=a; } } printf("%d\n",c); printf("%d",d); }*/ /* #include<stdio.h> int main() { int i; char c; for(;;) { scanf("%c", &c); printf("%c", c-32); } } */ /* #include <stdio.h> int main(){ int n,k,t,i; scanf("%d",&n); for(i=1;;i++){ if(n<i*i){ t=i-1; k=n-t*t; break; } } 1 > 1*1 > [1 < n] 2 > 2*2 > [4 < n] .. 6 > 6*6 > [36 > n] i-1 > 5 n - (i-1)*(i-1) > k printf("%d %d",k,t); } */ /* #include<stdio.h> int main() { int n; scanf("%d", &n); switch(n) { case 1: printf("111111111"); break; case 2: case 3: printf("33333333"); break; case 4: printf("4444"); case 5: printf("555555"); break; default: printf("0000000"); } } // 1202, 1207 switch ~ case */

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); 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%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<=170){ printf("CRASH"); } else if(b<=170){ printf("CRASH"); } else if(c<=170){ printf("CRASH"); } if(a>170&&b>170&&c>170){ printf("PASS"); } return 0; }*/ /* #include <stdio.h> int main(){ int a,b,y; scanf("%d %d",&a,&b); y=a/10000; if(b==1||b==2){ printf("%d",113-y); } else{ printf("%d",13-y); } return 0; }*/ /* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); if(b>=30){ printf("%d %d",a,b-30); } else{ if(a==0) { a=24; } printf("%d %d",a-1,b+30); } return 0; }*/ /* #include <stdio.h> int main(){ int a,b,c; scanf("%d %d %d",&a,&b,&c); if(a<b+c&&b<a+c&&c<a+b){ printf("yes"); } else { printf("no"); } return 0; }*/ /* #include <stdio.h> int main() { int a,b,c; scanf("%d %d %d",&a,&b,&c); if(c<a+b) { if(a==b&&b==c)3개 비교 안돼 { printf("정삼각형"); } else if(a==b||b==c) { printf("이등변삼각형"); } else if(a*a+b*b==c*c) { printf("직각삼각형"); } else { printf("삼각형"); } } else { printf("삼각형아님"); } return 0; }*/ /* #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,b; scanf("%d %d",&a,&b); if(a%5==0){ printf("%d",(90-a)/5+b); } else{ printf("%d",(90-a)/5+1+b); } return 0; }*/ /* #include <stdio.h> int main(){ int a,b,c,d; scanf("%d %d %d",&a,&b,&c); d=(a+b+c)/100%10; if(d%2==0){ printf("대박"); } else{ printf("그럭저럭"); } return 0; }*/ /* #include <stdio.h> int main(){ int n,a,b; scanf("%d",&n); b=n%10; a=n/10; n=(b*10+a)*2%100; printf("%d\n",n); if (n<=50){ printf("GOOD"); } else{ printf("OH MY GOD"); } return 0; }*/ /* #include <stdio.h> int main(){ int a,b,c,d; scanf("%d %d %d",&a,&b,&c); if(a%5==0){ d=(90-a)/5+b; } else{ d=(90-a)/5+1+b; } if(d==c){ printf("same"); } else if(d>c){ printf("win"); } else{ printf("lose"); } return 0; }*/ /* #include <stdio.h> int main(){ float a,b,c,d,e,f; scanf("%f %f %f %f",&a,&b,&c,&d); if(a/b==c/d){ printf("="); } else if(a/b>c/d){ printf(">"); } else{ printf("<"); } return 0; }*/ /* #include <stdio.h> int main(){ float a,b; scanf("%f %f",&a,&b); printf("%0.1f",a/b); return 0; }*/

/*#include <stdio.h> #include <stdlib.h> int main() { printf("Hello world!\n"); return 0; }*//* #include <stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d",x>y); return 0; }*//* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d",x==y); return 0; }*//* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a<=b); return 0; }*//* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a!=b); return 0; }*/ /* #include<stdio.h> int main(){ int a; scanf("%d",&a); printf("%d",!a); return 0; }*//* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a&&b); return 0; }*//* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a||b); return 0; }*//* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a!=b); return 0; }*/ /* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a&&b||!(a||b)); return 0; } */ /* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",!a&&!b); return 0; }*/ /* #include<stdio.h> int main() { printf("A B : (A&&B) \n"); printf("0 0 : %3d \n", (0&&0)); printf("0 1 : %3d \n", (0&&1)); printf("1 0 : %3d \n", (1&&0)); printf("1 1 : %3d \n", (1&&1)); }*/ /* #include <stdio.h> int main(){ int a; scanf("%d",&a); printf("%d",~a); return 0; }*/ // && || ! // !(a&&b) // & | ~ ^ /* #include <stdio.h> int main (){ int a,b; scanf("%d %d",&a,&b); printf("%d",a&b); return 0; }*/ /* #include<stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a|b); return 0; }*/ /* #include <stdio.h> int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d",a^b); return 0; }*/ /* #include<stdio.h> int main() { int a, b, c; scanf("%d %d", &a, &b); c = a>b ? a : b; printf("%d", c); }*/ /* #include <stdio.h> int main(){ int a,b,c; scanf("%d %d",&a,&b); c=a>b ? a : b ; printf("%d",c); return 0; }*/ /* #include <stdio.h> int main(){ int a,b,c,d; scanf("%d %d %d",&a,&b,&c); d=(a>b?b:a)>c?c:(a>b?b:a); printf("%d",d); return 0; }*/ /* #include<stdio.h> int main() { int n; scanf("%d", &n); if(n>5 && n<20) { // 6~19 printf("%d", n); } if(n<10 || n>30) { // ~9 // 30~ } /* if(n > 10) { if(n%2==0) { printf("JJ"); } else { printf("HH"); } printf("10"); } else if(n > 5) { printf("5"); } //////////////////////// printf("\n"); if(n%2==0) { printf("!!"); } else { printf("@@"); } } */ // 1153, 1154 /* #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{ printf("%d",b-a); } return 0; }*/

#include <stdio.h> #include <stdlib.h> /* int main() { printf("Hello world!\n"); return 0; }*/ /* #include <stdio.h> int main() { long long int x; scanf("%lld",&x); printf("%lld",x+1); return 0; }*/ /* #include<stdio.h> int main(){ long long int x,y; scanf("%lld %lld",&x,&y); printf("%lld\n%lld\n%lld\n%lld\n%lld\n%.2f",x+y,x-y,x*y,x/y,x%y,(float)x/y); return 0; }*/ /* #include<stdio.h> int main(){ int x,y,z; scanf("%d %d %d",&x,&y,&z); printf("%d\n%.1f",x+y+z,(x+y+z)/(float)3); return 0; }*/ /* #include<stdio.h> int main(){ int x; scanf("%d",&x); printf("%d",x); return 0; }*/ /* #include<stdio.h> int main(){ int x; scanf("%d",&x); printf("%d%%",x); return 0; }*/ /* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d %d",x,y); return 0; }*/ /* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d %d",y,x); return 0; }*//* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d",x+y); return 0; }*//* #include<stdio.h> int main (){ long long int x,y; scanf("%lld %lld",&x,&y); printf("%lld",x+y); return 0; }*//* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d+%d=%d\n%d-%d=%d\n%d*%d=%d\n%d/%d=%d",x,y,x+y,x,y,x-y,x,y,x*y,x,y,x/y); return 0; }*//* #include<stdio.h> int main(){ float x,y; scanf("%f %f",&x,&y); printf("%.2f",x*y); return 0; }질문 왜 int 함수 안되는지*/ /* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%.1f",x*y/(float)2); return 0; }*//* #include<stdio.h> int main(){ int x; scanf("%d",&x); printf("%d",x*24); return 0; }*//* #include<stdio.h> int main(){ int x,y,z; scanf("%d %d %d",&x,&y,&z); printf("%.2f",(x+y+z)/(float)3); return 0; }*//* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d",x%y); return 0; }*//* #include<stdio.h> int main(){ int x; scanf("%d",&x); printf("%d %d",x/10/6,x-(60*(x/10/6))); return 0; }*//* #include<stdio.h> int main(){ int x; scanf("%d",&x); printf("%.3f",(float)9/5*x+32); return 0; }*/

/* #include <stdio.h> int main() { printf("Hello\n"); return 0; } */ /* #include<stdio.h> int main() { printf("HELLO\tWORLKD"); return 0; }*/ /* #include<stdio.h> int main() { printf("Hello\tWorld"); return 0; }*/ /* #include<stdio.h> int main() { printf("Hello\nWorld"); return 0; }*/ /* #include<stdio.h> int main() { printf("'Hello'"); return 0; }*/ /* #include <stdio.h> int main(){ printf("\"Hello\tWorld\""); return 0;}*/ /* #include<stdio.h> int main(){ printf("\"!@#$%^&*()\""); return 0; }*/ /* #include<stdio.h> int main(){ printf("\"C:\\Download\\hello.cpp\""); return 0; }*/ /* // 정수 int %d (-2^31~+2^31-1) > -21억~ +21억 long long int %lld > ~~~ 2^63 // 실수 float %f double %lf // 문자 char %c > 2^8 -128 ~ +127 */ /* #include<stdio.h> int main() { char n; // ASCII scanf("%d", &n); printf("%c", n+32); return 0; }*/ /* #include<stdio.h> int main(){ int n; scanf("%d",&n); printf("%d",n); return 0; }*/ /* #include<stdio.h> int main(){ char n; scanf("%c",&n); printf("%c",n); return 0; }*/ /* #include<stdio.h> int main(){ float n; scanf("%f",&n); printf("%f",n); return 0; }*/ /* #include<stdio.h> int main(){ int ns,b; scanf("%d %d",&ns,&b); printf("%d %d",ns,b); return 0; }*/ /* #include<stdio.h> int main(){ char x,y; scanf("%c %c",&x,&y); printf("%c %c",y,x);// return 0; }*/ /* #include<stdio.h> int main(){ float n; scanf("%f",&n); printf("%.2f",n); return 0; }*/ /* #include<stdio.h> int main(){ int n; scanf("%d",&n); printf("%d %d %d",n,n,n); return 0; }*/ /* #include<stdio.h> int main(){ int x,y; scanf("%d:%d",&x,&y); printf("%d:%d",x,y); return 0; }*/ /* #include<stdio.h> int main(){ long long int x,y; scanf("%lld %lld",&x,&y); printf("%lld",x+y); return 0; }*/ /*#include<stdio.h> int main(){ int a; scanf("%d",&a); printf("%d",-a); return 0; }*/ /* #include<stdio.h> int main(){ char x; scanf("%c",&x); printf("%c",x+1); }*/ /* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d",x/y); return 0; }*/ /* #include<stdio.h> int main(){ int x,y; scanf("%d %d",&x,&y); printf("%d",x%y); return 0; }*/