/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
void rec(int n)
{
printf ("%d\n", n);
if(n==1) return ;
if(n%2==0)
{
rec(n/2);
}
else if(n%2==1)
{
rec(n*3+1);
}
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
}
*/
/*
#include <stdio.h>
void rec(int n)
{
if(n==1)
{
printf ("%d\n", n);
return;
}
if(n%2==1)
{
rec(n*3+1);
}
else if(n%2==0)
{
rec(n/2);
}
printf ("%d\n", n);
}
int main()
{
int n;
scanf("%d",&n);
rec(n);
}
rec(n) : 1부터 n까지의 합
: (1+2+3+4+.....+ n-1 )+ n
: rec(n-1) + n
rec(n) = rec(n-1) +n
1부터 n까지의 합 = 1부터 n-1까지의 합 + n
*/
/*
#include <stdio.h>
int rec(int n)
{
if(n==1) return 1;
return rec(n-1) + n;
}
int main()
{
int n;
scanf ("%d",&n);
printf("%d",rec(n));
}
*/
/*
#include <stdio.h>
int rec(int n)
{
if(n==1) return 1;
return rec(n-1) * n;
}
int main()
{
int n;
scanf ("%d",&n);
printf("%d",rec(n));
}
*/
/*
#include <stdio.h>
int rec(int n)
{
if(n==1||n==2) return 1;
return rec(n-1) + rec(n-2);
}
int main()
{
int n;
scanf ("%d",&n);
printf("%d",rec(n));
}
*/
/*
#include <stdio.h>
void star(int n)
{
if(n==0) return;
star(n-1);
printf ("*");
}//*을 n번 출력하는 재귀함수
void rec(int n)
{
if(n==0) return;
rec(n-1);
star(n);
printf ("\n");
}
int main()
{
int n;
scanf ("%d",&n);
rec(n);
}
*/
/*
#include <stdio.h>
void rec(int n)
{
if(n==0) return ;
rec(n/2);
printf ("%d", n%2);
}
int main()
{
int n;
scanf ("%d",&n);
if(n==0)
{
printf("0");
return 0;
}
rec(n);
return 0;
}
*/
//memoization 메모이제이션
//계산했던 결과를 저장해서 다시 계산하지 않도록 하는 기법!
//memo[n] = n번째 피보나치수
/*
#include <stdio.h>
int memo[201]={};
int rec(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1||n==2) return memo[n]=1;
return memo[n]=(rec(n-1) + rec(n-2))%10009;
}
int main()
{
int n;
scanf ("%d",&n);
printf("%d",rec(n));
}
*/
/*
#include <stdio.h>
int memo[51][51] = {0};
int rec(int r,int c)
{
if(memo[r][c]!=0) return memo[r][c];
if(r==1||c==1) return memo[r][c]=1;
return memo[r][c] = (rec(r-1,c)+rec(r,c-1))%100000000;
}
int main()
{
int r,c;
scanf ("%d %d",&r,&c);
printf ("%d",rec(r,c));
}
#include <stdio.h>
typedef struct
{
char name[11];
int a;
int b;
int c;
}student;
int main()
{
student st[101];
int n,i,max=0;
scanf ("%d",&n);
for(i=0; i<n; i++)
{
scanf ("%s %d %d", st[i].name,&st[i].a,&st[i].b,&st[i].c);
}
for(i)
printf ("%s %d %d",st[i].a,st[i].b,st[i].c);
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
int a;
int b;
}student;
int main()
{
student st[201];
int i,j,n,s=1;
scanf ("%d",&n);
for(i=0; i<n; i++)
{
scanf ("%d", &st[i].a);
}
for(i=0;i<n;i++)
{
s=1;
for(j=0;j<n;j++)
{
if(st[i].a<st[j].a)
{
s++;
}
}
st[i].b=s;
printf ("%d %d\n", st[i].a,st[i].b);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
}
*/