//#include<stdio.h>
//
//int n,k,d[1010];
//
//int lower_bound(int p)
//{
// for(int i=1; i<=n; i++)
// {
// if(k<=d[i])
// {
// p=i;
// break;
// }
// else if(k>d[n])
// {
// p=n+1;
// break;
// }
// }
// return p;
//}
//
//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));
//
//
//
//}
//#include<stdio.h>
//double f(){
//
//
// return 3.1415926535897;
// }
//int main(){
//
// printf("%.13lf",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");
// return;
//
//
// }
//int main(){
//
// scanf("%d",&n);
// f(n);
// return 0;
//
// }
//#include<stdio.h>
//
//int n;
//
//void f(int x){
//
// if(x%2==1)printf("odd\n");
// else printf("even\n");
// return;
// }
//
//int main(){
//
// scanf("%d",&n);
// f(n);
// return 0;
//
// }
//#include<stdio.h>
//
//int n;
//
//void f(int x){
//
// if(x==0)printf("false");
// else printf("true");
//
// }
//
//int main(){
//
// scanf("%d",&n);
// f(n);
// return 0;
//
//
// }
//#include<stdio.h>
//
//int n;
//
//void f(int x){
//
// if(x==0)printf("zero");
// else printf("non zero");
// }
//
//int main(){
//
// scanf("%d",&n);
// f(n);
// return 0;
//
// }
//#include<stdio.h>
//
//int n;
//
//void f(int x){
//
// if(x<0)printf("negative");
// else if(x>0)printf("positive");
// else printf("zero");
//
// }
//
//int main(){
// scanf("%d",&n);
// f(n);
// return 0;
//
// }
//#include<stdio.h>
//
//int n;
//
//void f(int x)
//{
// int i,cnt=0;
// for(i=1; i<=x; i++)
// {
// if(x%i==0)cnt++;
// }
// if(cnt==2)printf("prime");
// else printf("composite");
//
//}
//
//int main()
//{
//
// scanf("%d",&n);
// f(n);
// return 0;
//
//}
//#include<stdio.h>
//
//int n;
//
//void f(int x)
//{
//
// int i;
// for(i=0; i<n; i++)
// {
// printf("love\n");
// }
//
//}
//
//int main()
//{
//
// scanf("%d",&n);
// f(n);
// return 0;
//
//}
//#include<stdio.h>
//
//int n;
//
//void f(int x){
//
// int i;
// for(i=0; i<n; i++){
// printf("*");
// }
//
// }
//
//int main(){
//
// scanf("%d",&n);
// f(n);
// return 0;
//
// }
//#include<stdio.h>
//
//
//int n;
//#include<stdbool.h>
//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>
//
//int n;
//
//#include<stdbool.h>
//bool zero(int k){
// return !k;
// }
//bool plus(int k){
//
// return k>0;
// }
//
//int main(){
//
// scanf("%d",&n);
// if(zero(n))printf("zero");
// else printf("%s",plus(n)?"plus":"minus");
// return 0;
//
//
// }
//#include<stdio.h>
//
//int n;
//
//#include<stdbool.h>
//bool prime(int k){
//
// int i;
// for(i=2; i<k; i++)
// if(k%i==0)
// break;
// return i==k;
// }
//
//int main(){
//
// scanf("%d",&n);
// if(prime(n))printf("prime");
// else printf("composite");
// return 0;
//
//
// }
//#include<stdio.h>
//
//char grade (int x)
//{
//
// switch (x/10)
// {case 10:
// case 9:
// return 'A';
// break;
// case 8:
// return 'B';
// break;
// case 7:
// return 'C';
// break;
// case 6:
// return 'D';
// break;
// default:
// return 'F';
// break;
// }
//
//}
//
//int n;
//
//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 k){
//
// if(k>0)return k;
// else if(k<0)return -k;
// else return 0;
// }
//
//int main(){
//
// scanf("%lld",&n);
// printf("%lld\n",abs(n));
// return 0;
//
// }
//#include<stdio.h>
//
//long long int n;
//
//long long int sqrt(long long int x)
//{
//
// for(long long i=0; i<=x; i++)
// {
// if(x<i*i)
// {
// return i-1;
// break;
// }
// if(x==i*i)
// {
// return i;
// break;
// }
// }
//
//}
//
//int main()
//{
//
// scanf("%lld",&n);
// printf("%d\n",sqrt(n));
// return 0;
//
//}
//#include<stdio.h>
//
//int n,d[100010], k;
//
//int f(int x)
//{
// int loc=0,cnt=0;
// for(int i=1; i<=n; i++)
// {
// if(d[i]==x)
// {
// loc=i;
// return loc;
// break;
// }
// else
// cnt++;
// }
// if(cnt==n)
// 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 t)
//{
//
// return x-(long long int)t;
//}
//
//int main()
//{
//
// scanf("%1f",&x);
// printf("%.14f\n",f(x));
//
//}
//#include<stdio.h>
//
//double x;
//
//long long int f(double x){
// long long int t=(long long int)x;
//
// if(t<x)return x+1;
// else return x;
// }
//
//int main(){
//
// scanf("%lf",&x);
// printf("%lld\n",f(x));
//
// }
//#include<stdio.h>
//
//double x;
//
//long long int f(double x)
//{
// long long int t=(long long int)x;
//
// if(t<x)
// return x;
// else if(t==x)
// return x;
// else return x-1;
//}
//
//int main()
//{
//
// scanf("%lf",&x);
// printf("%lld\n",f(x));
//
//}