250805
//#include<stdio.h>
//
//int memo[10000] = {0};
//int p = 0;
//
//int fibo(int k) {
// if(k <= 2) {
// p++;
// return memo[k] = 1;
// }
//
// if(memo[k] != 0) {
// return memo[k];
// }
//
// return memo[k] = fibo(k-1)%10009 + fibo(k-2)%10009;
//}
//
////void f(int k) {
//// if(k==0){
//// return;
//// }
//// f(k-1);
//// printf("%d\n", k);
////}
//
//int main() {
// int n;
//
// scanf("%d", &n);
//// f(n);
//
// printf("%d\n", fibo(n)%10009);
// printf("Excute time is %d\n", p);
// return 0;
//}
/* ¿ì¹Ú¼ö (3n+1) basic
#include<stdio.h>
int clz(int k){
int t = 0;
if(k == 1) {
printf("%d",k);
return;
}
if(k % 2 == 1){
t = 3 * k + 1;
}
if(k % 2 == 0){
t = k / 2;
}
printf("%d\n", k);
clz(t);
return t;
}
int main(){
int n;
scanf("%d", &n);
clz(n);
return 0;
}
*/
/*
#include<stdio.h>
int clz(int k){
int t = 0;
if(k == 1) {
printf("%d\n",k);
return;
}
if(k % 2 == 1){
t = 3 * k + 1;
}
if(k % 2 == 0){
t = k / 2;
}
clz(t);
printf("%d\n", k);
return t;
}
int main(){
int n;
scanf("%d", &n);
clz(n);
return 0;
}
*/
/*
#include<stdio.h>
void p(int l){
if(l < 0) {
printf("\n");
return;
}
printf("*");
l--;
p(l);
return l;
}
void tri(int k){
if (k < 1){
return;
}
k--;
tri(k);
p(k);
return k;
}
int main(){
int n;
scanf("%d", &n);
tri(n);
return 0;
}
*/
/*
#include<stdio.h>
int r, c;
int m[100][100] = {};
int f(r, c){
if(r == 1 || c == 1){
return m[r][c] = 1;
}
if (m[r][c] != 0){
return m[r][c];
}
return m[r][c] = f(r-1, c)%100000000 + f(r, c-1)%100000000;
}
int main(){
scanf("%d %d", &r, &c);
printf("%d", f(r, c)%100000000);
}
*/
/*
#include<stdio.h>
void print(int k, char a, char b){
printf("Disk %d : %c to %c\n", k, a, b);
return;
}
void f(int k, char a, char b, char c){
if (k == 1){
print(k, a, c);
return;
}
f(k-1, a, c, b);
print(k, a, c);
f(k-1, b, a, c);
}
int main(){
int n;
scanf("%d", &n);
f(n, 'A', 'B', 'C');
}
*/
/*
#include <stdio.h>
int N, M;
int arr[1000000] = {0};
int brr[1000000] = {0};
int r = 0;
int d(int L, int R, int m){
if (arr[i] > brr[m]){
d(m+1, R, (L+R)/2);
}
if (arr[i] < brr[m]){
R = m-1;
m = ( L + R ) / 2;
d(m+1, R, (L+R)/2);
}
if (arr[i] == brr[m]){
r++;
}
}
int e(int m){
}
int main(){
scanf("%d", &N);
for(int i=0;i<N;i++){
scanf("%d", arr[i]);
}
scanf("%d", &M);
for(int i=0;i<M;i++){
scanf("%d", brr[i]);
}
int L = 0;
int R = N-1;
int m = (L+R)/2;
d(L, R, m);
}
*/
/*
#include <stdio.h>
int arr[1000001] = {0};
int d(int L, int R, int x){
if(L > R){
return -1;
}
int m = (L + R) / 2;
if(x < arr[m]){
return d(L, m - 1, x);
}
else if(x > arr[m]){
return d(m + 1, R, x);
}
else{
return m + 1;
}
}
int main(){
int x;
int N;
int M;
scanf("%d", &N);
for(int i = 0; i < N; i++){
scanf("%d", &arr[i]);
}
scanf("%d", &M);
for(int i = 0; i < M; i++){
scanf("%d", &x);
printf("%d ", d(0, N - 1, x));
}
return 0;
}
*/
/*
#include<stdio.h>
int res = 0;
int f(int k){
if (k == 1){
return ++res;
}
f(k-1);
f(k-1);
res++;
}
int main(){
int n;
scanf("%d", &n);
printf("%d", f(n));
return 0;
}
*/
/*
#include<stdio.h>
unsigned long long int b = 1;
unsigned long long int f(unsigned long long int k){
if(k % 2 == 1){
return b;
}
return f(k / 2) + b;
}
int main(){
unsigned long long int n;
scanf("%llu", &n);
printf("%llu\n", f(n));
return 0;
}
*/
/*
#include<stdio.h>
int main() {
int n = 10;
int *pn = &n;
printf("Value is %d\n", n);
printf("N Address is %d(%p)\n", &n, &n);
printf("pointer N Value is %d\n", pn); // address
printf("pointer inside value is %d\n", *pn);
printf("pointer N Address is %d(%p)\n\n\n", &pn, &pn);
int data[5] = {10, 20, 30, 40, 50};
int *pArr = data;
printf("data[0] value is %d (%p, %p)\n", data[0], &data[0], data);
printf("pArr -> %p(%d)\n", pArr, *pArr);
printf("pArr + 1: %p(%d)\n", pArr+1, pArr+1);
printf("pArr + 1: %p(%d)\n", *pArr+1, *pArr+1);
printf("pArr + 1: %p(%d)\n", *(pArr+1), *(pArr+1));
}
*/
/*
#include <stdio.h>
void myswap(int *a, int *b){
if (*b>*a){
return;
}
int c = *a;
*a = *b;
*b = c;
return ;
}
int main(){
int a, b;
scanf("%d %d", &a, &b);
myswap(&a, &b);
printf("%d %d", a, b);
return 0;
}
*/
/*
#include <stdio.h>
int main(){
int N;
scanf("%d", &N);
int SN = N;
int Sarr = 0;
int *arr = (int*)malloc(N*(sizeof(int)));
for(int i = 1; i < N; i++){
scanf("%d", &arr[i]);
SN += i;
Sarr += arr[i];
}
printf("%d", SN - Sarr);
return 0;
}
*/
/*
#include<stdio.h>
struct stdentInfo {
char name[100];
int age;
double height;
};
// 100 > 212
typedef struct student{
} student;
int main() {
struct stdentInfo x;
struct stdentInfo classroom[100];
student xx;
student *ppx = &x;
scanf("%d", &x.age);
scanf("%d", &classroom[0].age);
}
*/
/**
5명 학생정보
이름, 국, 수, 영 / 학생 평균 1등 과목 평균 1등
**/