/*
#include <stdio.h>
int a, n;
long long int pow(int a, int n)
{
int i;
long long int s=1;
if(a==1)
{
return 1;
}
else
{
for(i=1; i<=n; i++)
{
s*=a;
}
}
return s;
}
int main()
{
scanf("%d%d", &a, &n);
printf("%lld\n", pow(a, n));
}
*/
/*
#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)
{
return (long long int)a*b/gcd(a,b);
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", lcm(a, b));
}
*/
/*
#include <stdio.h>
long long int n;
long long int f(long long int n)
{
long long int i,disi=1,total=0;
while(n>0)
{
total=total*10+n%10;
n=n/10;
}
return total;
}
int main()
{
scanf("%lld", &n);
printf("%lld\n", f(n));
}
*/
/*
#include <stdio.h>
long long int n;
int sqrt(long long int n)
{
int i;
for(i=1;i<=n;i++)
{
if((long long int)i*i>n)
{
break;
}
}
return i-1;
}
int main()
{
scanf("%lld", &n);
printf("%d\n", sqrt(n));
return 0;
}
//재귀함수 1. 종료조건 2.점화식
void f(int n)
{
if(n==0) return ;
printf("%d\n",n);
f(n-1);
}
*/
/*
#include <stdio.h>
f(n) : n부터 1까지 출력해라
print n -> print n-1 -> print n-2 -> ..... print 1
print n -> f(n-1);
f(n) : 1부터 n까지 출력
(print 1 -> print 2 -> .... -> print n-1) -> print n
f(n-1); ->print n
void f(int n)
{
if(n==0) return ;
f(n-1);
printf("%d\n",n);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return ;
printf("%d\n",n);
f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}
*/
/*
#include <stdio.h>
void f(int min, int n)
{
if(n<min) return ;
f(min,n-1);
if(n%2==1) printf("%d ",n);
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
f(a,b);
}
*/
/*
#include <stdio.h>
void f(int n)
{
printf("%d\n",n);
if(n==1)
return ;
if(n%2==1)
f(3*n+1);
else
f(n/2);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}
*/
/*
#include <stdio.h>
void star(int n)
{
if(n==0) return ;
printf("*");
star(n-1);
}
void f(int n)
{
if(n==0) return ;
f(n-1);
star(n);
printf("\n");
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==1)
{
printf("1\n");
return ;
}
if(n%2==1)
f(3*n+1);
else
f(n/2);
printf("%d\n",n);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
}
*/
/*
f(n) : 1 + 2 + ... + n 를 리턴
(1+2+...+n-1 +n)을 리턴
n + f(n-1)을 리턴
if(n==1) return 1;
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1)
{
return 1;
}
return n+f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1) return 1;
return n*f(n-1);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1||n==2) return 1;
return f(n-1)+f(n-2);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/
/*
#include <stdio.h>
int m[201]={};
int f(int n)
{
if(m[n]!=0) return m[n];
if(n==1||n==2) return m[n]=1;
return m[n]=(f(n-1)+f(n-2))%10009;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
}
*/