//#include<stdio.h>
//#include<string.h>
//int k(char *str, int a)
//{
// int i;
// for(i=0; i<strlen(str); i++)
// {
// a+=str[i];
// }
// return a;
//}
//int main()
//{
// int i, a;
// char str[10000000];
// scanf("%s", str);
// for(i=0; i<3; i++)
// {
// if(1<strlen(str))
// {
// k(str, a);
// }
// }
// printf("%d", a);
// return 0;
//}
//
//#include <stdio.h>
//char f()
//{
// char a='A';
// 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("word");
// }
// return;
//}
//
//// 이 부분에 들어가야 될 코드를 작성하여 제출
//main()
//{
// scanf("%d", &n);
// f(n);
// return 0;
//}
//#include <stdio.h>
//
//int n;
//void f(int n)
//{
// if(n%2==1)
// {
// printf("odd");
// }
// else if (n%2==0)
// {
// printf("even");
// }
// return;
//}
//int main()
//{
// scanf("%d", &n);
// f(n);
// return 0;
//}
//#include <stdio.h>
//
//int n;
//void f(int n)
//{
// if(n==0)
// {
// printf("false");
// }
// else
// {
// printf("true");
// }
// return;
//}
//
//// 이 부분에 들어가야 될 코드를 작성하여 제출
//int main()
//{
// scanf("%d", &n);
// f(n);
// return 0;
//}
//#include <stdio.h>
//
//int n;
//void f(int n)
//{
// if(n==0)
// {
// printf("zero");
// }
// else if(n<0)
// {
// printf("negative");
// }
// else
// {
// printf("positive");
// }
// 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("love \n");
// }
// return;
//}
//int main()
//{
// scanf("%d", &n);
// f(n);
// return 0;
//}
//void f(int n)
//{
// int i;
// for(i=1; i<=n; i++)
// {
// printf("*");
// }
// return;
//}
//#include <stdio.h>
//
//int n;
//
//int main()
//{
// scanf("%d", &n);
// if(zero(n))
// printf("zero");
// else
// printf("non zero");
// return 0;
//}
//#include <stdio.h>
//#include<stdbool.h>
//int n;
//bool zero(int k)
//{
// return !k;
//}
//int main()
//{
// scanf("%d", &n);
// if(zero(n)) printf("zero");
// else printf("non zero");
// return 0;
//}
//#include <stdio.h>
//#include<stdbool.h>
//int n;
//bool prime(int j)
//{
// int i=2;
// for(i=2; i<j; i++) //1과 자기 자신 빼고 약수를 가지는지 검사
// {
// if(j%i==0)
// break; //약수를 가질 경우(나누어 떨어진다) 반복 벗어나기
// }
// return i==j; //반복을 벗어나지 못해 i와 j가 같아졌는지에 대한 논리값 반환
//}
//int main()
//{
// scanf("%d", &n);
// if(prime(n))
// printf("prime");
// else
// printf("composite");
// return 0;
//}
//#include <stdio.h>
//
//int n;
//
//char grade(int a)
//{
// if(a>=90)
// {
// return'A';
// }
// else if(a>=80)
// {
// return'B';
// }
// else if(a>=70)
// {
// return'C';
// }
// else if(a>=60)
// {
// return'D';
// }
// else
// {
// return'F';
// }
//}
//int main()
//{
// scanf("%d", &n);
// printf("%c", grade(n));
// return 0;
//}
//#include <stdio.h>
//
//long long int n;
// int abs(int n)
//{
// if (0<=n)
// {
// return n;
// }
// else if(0>n)
// {
// return n*-1;
// }
//
//}
//int main()
//{
// scanf("%lld", &n);
// printf("%lld\n", abs(n));
// return 0;
//}
//#include <stdio.h>
//int mymax(int a, int b)
//{
// if(a>=b)
// {
// return a;
// }
// else
// {
// return b;
// }
//}
//main()
//{
// int a, b;
// scanf("%d %d", &a, &b);
// printf("%d", mymax(a, b));
//}
//#include <stdio.h>
//int myabs(int n)
//{
// if(n<=0)
// {
// return n*-1;
// }
// else
// {
// return n;
// }
//
//}
//main()
//{
// int a;
// scanf("%d", &a);
// printf("%d", myabs(a));
//}
//void f()
//{
// printf("Hello?");
//}
//#include <stdio.h>
//
//int n, k, d[1010];
//int upper_bound(int k)
//{
// int i;
//
// for(i=1;i<=n;i++)
// {
// if(d[i]>=k)
// {
// return i;
// break;
// }
// }
// return n+1;
//}
//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>
//int n;
////int f(int n)
////{
//// int i, a;
//// for(i=1;i<=n;i++)
//// {
//// a*=i;
//// }
//// return a;
////}
//long long int f(long long int n) {
// if (n == 1)
// return 1;
// return n*f(n-1);
//}
//int main()
//{
// scanf("%d", &n);
// printf("%lld\n", f(n));
//}
//#include <stdio.h>
//
//int n;
//int f(int n)
//{
// int sum=0, i;
// for(i=1;i<=n;i++)
// {
// if(n%i==0)
// {
// sum++;
// }
// }
// return sum;
//}
//int main()
//{
// scanf("%d", &n);
// printf("%d\n", f(n));
//}
//#include <stdio.h>
//
//int n, d[100010], k;
//////////////////////////
//int f(int k)
//{
// int i;
// for(i=1;i<=n;i++)
// {
// if(d[i]==k)
// {
// return i;
// break;
// }
// }
// 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));
//}
//#include <stdio.h>
//
//double x;
//
//double f(double x)
//{
// int a=x;
// x-=a;
// return x;
//}
//int main()
//{
// scanf("%lf", &x);
// printf("%.14lf\n", f(x));
//}
//#include <stdio.h>
//
//double x;
//
//int f(float x)
//{
// int a=x;
// float b=x-a;
// if(b>=0.5)
// {
// return a+1;
// }
// else
// {
// return a;
// }
//}
//int main()
//{
// scanf("%lf", &x);
// printf("%lld\n", f(x));
//}
//#include <stdio.h>
//
//int n, m;
//long long int f(long long int n, long long int m)
//{
// return n+m;
//}
//int main()
//{
// scanf("%d%d", &n, &m);
// printf("%lld\n", f(n, m));
//}
//#include <stdio.h>
//
//int n, m;
//long long int f(long long int a, long long int b) {
// //삼항 연산자 사용
// if (b < a)
// return (long long int)a - (long long int)b;
// else
// return (long long int)b - (long long int)a;
//}
//int main()
//{
// scanf("%d%d", &n, &m);
// printf("%lld\n", f(n, m));
//}
//#include <stdio.h>
//
//int n, m;
//int min (int n, int m)
//{
// if(n<=m)
// {
// return n;
// }
// else