/*
#include <stdio.h>
int n, a, b, d[1010];
int maxi()
{
int max=0,c=a;
max=d[a];
for(int i=a;i<=b;i++)
{
if(max<d[i])
{
max=d[i];
c=i;
}
}
return c;
}
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 n, k, d[1010];
int lower_bound()
{
int c=0;
for(int i=1;i<=n;i++)
{
if(k>d[i])
{
c=i;
}
}
c+=1;
return c;
}
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));
}
recursive function 재귀함수
f(n) : n부터 1까지 출력하는 함수
n출력 -> n-1부터 1까지 출력
n 출력 -> f(n-1)
g(n) : 1부터 n까지 출력하는 함수
1부터 n-1까지 출력 -> n출력
g(n-1) -> n출력
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return ; //종료조건
printf("%d\n",n);
f(n-1); //재귀호출
}
int main()
{
f(10);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return ;
f(n-1);
printf("%d\n",n);
return ;
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
int n;
void f(n)
{
if(n==0) return ;
printf("%d\n",n);
f(n-1);
return ;
}
int main()
{
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int a,int b)
{
if(b==a-1) return ;
f(a,b-1);
if(b%2!=0) printf("%d ",b);
return ;
}
int main()
{
int a,b;
scanf("%d %d",&a,&b);
f(a,b);
return 0;
}
f(n) : return (1+2+3+4+ ...+n);
: return (1+2+3+....+n-1 + n);
: return f(n-1)+n;
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1) return 1;
return f(n-1)+n;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",f(n));
return 0;
}
*/
/*
#include <stdio.h>
long long int f(int n)
{
if(n==1) return 1;
return f(n-1)*n;
}
int main()
{
int n;
scanf("%d",&n);
printf("%lld",f(n));
return 0;
}
*/
/*
#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));
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==1) return 1;
else if(n%2==0)
{
printf("%d\n",n/2);
f(n/2);
return ;
}
else
{
printf("%d\n",3*n+1);
f(3*n+1);
return ;
}
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==1) return 1;
else if(n%2==0)
{
f(n/2);
printf("%d\n",n/2);
return ;
}
else
{
f(3*n+1);
printf("%d\n",3*n+1);
return ;
}
}
int main()
{
int n;
scanf("%d",&n);
f(n);
printf("%d",n);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return ;
printf("*");
f(n-1);
return ;
}
void g(int n)
{
if(n==0) return ;
g(n-1);
f(n);
printf("\n");
return ;
}
int main()
{
int n;
scanf("%d",&n);
g(n);
return 0;
}
*/
/*
#include <stdio.h>
int f(int n)
{
if(n==1||n==0)
{
printf("%d",n);
return ;
}
f(n/2);
printf("%d",n%2);
return ;
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
int memo[22][22]={};
int SuperSum(int k,int n)
{
if(memo[k][n]!=0) return memo[k][n];
if(k==0) return memo[0][n]=n;
if(n==1) return memo[k][1]=1;
return memo[k][n]=SuperSum(k,n-1)+SuperSum(k-1,n);
}
int main()
{
int k,n;
while( scanf("%d %d", &k, &n) != EOF )
printf("%d\n", SuperSum(k, n));
return 0;
}
*/