/*
#include <stdio.h>
#include <stdlib.h>
void f1(int n)
{
if(n%2==1)
{
printf("%d\n", 3*n+1);
n=3*n+1;
}
else
{
printf("%d\n", n/2);
n=n/2;
}
return f(n);
}
void f(int n)
{
if(n!=1)
{
return f1(n);
}
else
return 0;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
#include <stdlib.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);
return 0;
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
void f(int n)
{
if(n!=1)
{
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);
return 0;
}
#include <stdio.h>
int memo[201]={};
int f(int N)
{
if(memo[N]!=0) return memo[N];
if(N==1 || N==2) return memo[N]=1;
return memo[N]=(f(N-1)+f(N-2))%10009;
}
int main()
{
int N;
scanf("%d", &N);
printf("%d", f(N));
return 0;
}
*/
/*
#include <stdio.h>
int memo[51][51]={};
int f(int a, int b)
{
if(memo[a][b]!=0) return memo[a][b];
if(a==1 || b==1) return memo[a][b]=1;
return memo[a][b]=(f(a-1, b)+f(a, b-1))%100000000;
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d", f(a, b));
return 0;
}
*/
/*
#include <stdio.h>
int memo[100001]={};
int f(int n)
{
if(memo[n]!=0) return memo[n];
if(n==1) return memo[n]=1;
else if(n==2) return memo[n]=2;
else if(n==3) return memo[n]=4;
return memo[n]=(f(n-1)+f(n-2)+f(n-3))%1000;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n));
return 0;
}
*/
/*
#include <stdio.h>
int memo[10000001]={}, max=0, max_idx;
int f2(int b)
{
if(b!=1)
{
if(b%2==1)
{
memo[b]=f2(3*b+1);
}
else
{
memo[b]=f2(b/2);
}
}
return f2(b);
}
int f1(int a, int b)
{
if(a>b) return;
if(max>memo[b])
{
max=memo[b];
max_idx=b;
}
else if(max==memo[b] && max_idx>b)
{
max=memo[b];
max_idx=b;
}
return f1(a, b-1);
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
f2(b);
printf("%d %d", max_idx, max);
return 0;
}
*/
/*
#include <stdio.h>
void f(int* pa)
{
(*pa)++;
}
int main()
{
int a=10;
f(&a);
printf("a : %d\n",a);
}
//int main()
//{
// int a=10;
//
// printf("a : %d\n",a);
// printf("&a : %d\n",&a);
//
// int* pa;
// pa=&a;
// printf("pa : %d\n",pa);
// //*간접참조연산자
// printf("*pa : %d\n",*pa);
//}
*/
/*
#include <stdio.h>
void myswap(int* pa, int*pb)
{
int temp;
if(*pa>*pb)
{
temp=*pa;
*pa=*pb;
*pb=temp;
}
}
main()
{
int a, b;
scanf("%d%d", &a, &b);
myswap(&a, &b);
printf("%d %d", a, b);
}
char* mysubstr(char *str, int start, int count)
{
// str[start+count]=0;
*(str+start+count)=0;
//str[n] *(str+n)
return str+start;
}
*/
/*
#include <stdio.h>
char *mysubstr(char *str, int start, int count)
{
str[start+count]=0;
return &str[start];
}
int main()
{
char str[100];
int a, b;
scanf("%s", str);
scanf("%d %d", &a, &b);
printf("%s", mysubstr(str, a, b));
}
*/