/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int a, b;
int gcd(int a,int b)
{
int i;
for(i=(a>b?b:a);i>=1;i--){
if(a%i==0&&b%i==0){
return i;
}
}
}
int main()
{
scanf("%d%d", &a, &b);
printf("%d\n", gcd(a, b));
}
*/
/*
#include <stdio.h>
int gcd(int p, int q){ if(p==0) return q; return gcd(q%p, p);}
long long int lcm(long long int a,long long int b)
{
return a*b/gcd(a,b);
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", lcm(a, b));
}
*/
/*
char *mysubstr(char *str, int start, int count)
{
int i;
for(i=start;i<start+count-1;i++){
return i
}
}*/
/*
#include <stdio.h>
int a;
int f()
{
int sum=0;
for(;;)
{
sum=0;
for(;;)
{
sum+=a%10;
a/=10;
if(a==0)
{
break;
}
}
if(sum<10) return sum;
else a=sum;
}
}
int main()
{
scanf("%d",&a);
printf("%d",f());
return 0;
}
*/
/*
#include <stdio.h>
double f(double a)
{
if(a>=0){
return a;
}
else{
return a*-1;
}
}
int main()
{
double a;
scanf("%lf",&a);
printf("%.10g",f(a));
}
*/
/*
#include <stdio.h>
int n, a, b, d[1010];
int maxi(int x,int y)
{
int i,loc, max=d[x];
loc = x;
for(i=x;i<=y;i++){
if(max<d[i]){
max=d[i];
loc = i;
}
}
return loc;
}
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 a,n;
long long int pow(int a,int n)
{
long long int m=1;
if(a==1)
{
return 1;
}
for(int i=0; i<n; i++)
{
m*=(long long int)a;
}
return m;
}
int main()
{
scanf("%d%d", &a, &n);
printf("%lld\n", pow(a, n));
}
*/
/*
#include <stdio.h>
long long int n;
int sqrt(int n)
{
int a,i;
for(i=0;i*i<n;i++){
return a;
}
}
int main()
{
scanf("%lld", &n);
printf("%d\n", sqrt(n));
return 0;
}
*/