#include <stdio.h>
#include <stdlib.h>
/*
float f(float a)
{
if (a<0)
{
a=-a;
}
return a;
}
int main()
{
float n;
scanf("%f",&n);
if(n>999999 || n<-999999)
{
printf("%.10g",f(n));
}
else
{
printf("%g",f(n));
}
}
*/
/*
int f(int a)
{
a=a/1000000+a/100000%10+a/10000%10+a/1000%10+a/100%10+a/10%10+a%10;
if(a<10)
{
return a;
}
else
{
f(a);
}
}
main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
int n, k, d[1010];
int upper_bound(int k)
{
for(int i=1; i<=n; i++)
{
if(d[i]>k)
{
return i;
}
else if(i==n)
{
return i+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));
}
*/
/*
int n, k, d[1010];
int lower_bound(int k)
{
for(int i=1; i<=n; i++)
{
if(d[i]>=k)
{
return i;
}
else if(i==n)
{
return i+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));
}
*/
/*
int n, k, d[1010];
int findi(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", findi(k));
}
*/
/*
int n, a, b, d[1010];
int x,y;
int maxi(int a, int b)
{
x=d[a];
y=a;
for(int i=a; i<=b; i++)
{
if(d[i]>x)
{
x=d[i];
y=i;
}
}
return y;
}
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));
}
*/
/*
int n, a, b, d[1010];
long long int x=0;
long long int subsetsum(int a, int b)
{
for(int i=a; i<=b; i++)
{
x+=d[i];
}
return x;
}
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));
}
*/
/*
int a, n;
long long int x=1;
long long int pow(int a, int n)
{
if(a==1 || a==0)
{
return 1;
}
for(int i=1; i<=n; i++)
{
x=x*a;
}
return x;
}
int main()
{
scanf("%d %d", &a, &n);
printf("%lld\n", pow(a, n));
}
*/