/*#include <stdio.h>
int n;
long long int f(int n)
{
long long int sum=0;
for(int i=1;i<=n;i++)
{
sum+=i;
}
return sum;
}
int main()
{
scanf("%d", &n);
printf("%lld\n", f(n));
}
*/
/*
#include <stdio.h>
int n;
long long int f(int n)
{
long long int a=1;
for(int i=1;i<=n;i++)
{
a*=i;
}
return a;
}
int main()
{
scanf("%d", &n);
printf("%lld\n", f(n));
}
*/
/*
#include <stdio.h>
int n, k, d[1010];
int upper_bound(int k)
{
int flag=0;
for(int i=1;i<=n;i++)
{
if(d[i]>k)
{
flag=1;
return i;
}
}
if(flag==0)
return n+1;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
scanf("%d", &k);
printf("%d\n", upper_bound(k));
}
*/
/*
#include <stdio.h>
double ABS(double n)
{
if (n<0)
{
n*=-1;
}
return n;
}
int main()
{
double n;
scanf("%lf", &n);
printf("%.10g", ABS(n));
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
int math, info;
}score;
int main()
{
int arr1[1001], n, a;
score arr[1001], temp;
scanf("%d", &n);
for(int i=1;i<=n;i++)
{
arr1[i]=i;
scanf("%d %d", &arr[i].math, &arr[i].info);
}
for(int i=0;i<n-1;i++)
{
for(int j=1;j<=n-1-i;j++)
{
if(arr[j].math<arr[j+1].math)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
a=arr1[j];
arr1[j]=arr1[j+1];
arr1[j+1]=a;
}
else if(arr[j].math==arr[j+1].math)
{
if(arr[j].info<arr[j+1].info)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
a=arr1[j];
arr1[j]=arr1[j+1];
arr1[j+1]=a;
}
}
else if(arr[j].math==arr[j+1].math && arr[j].info==arr[j+1].info)
{
if(arr1[j]<arr1[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
a=arr1[j];
arr1[j]=arr1[j+1];
arr1[j+1]=a;
}
}
}
}
for(int i=1;i<=n;i++)
{
printf("%d %d %d\n", arr1[i], arr[i].math, arr[i].info);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, n1;
long long int a=1, b=0;
scanf("%d", &n);
n1=n;
while(n1>0)
{
if(n1%2!=0)
{
b=b+(n1%2)*a;
}
n1/=2;
a*=10;
}
printf("2 %lld\n", b);
printf("8 %o\n", n);
printf("16 %X\n", n);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int h, m, gap;
scanf("%d %d", &h, &m);
scanf("%d", &gap);
m+=gap;
h+=m/60;
m%=60;
h%=24;
printf("%d %d", h, m);
return 0;
}
재귀함수 : 함수 내에서 자신을 호출하는 함수
: 자신으로 다시 정의내리는 함수
재귀함수 만드는연습 -> 적용
void f(int n)
{
for(int i=n;i>=1;i--) printf("%d ",i);
}
*/
//#include <stdio.h>
//f(n) : n부터 1까지 출력
// : n 출력 -> n-1 부터 1까지 출력
// : n 출력 -> f(n-1) (n>=1)
//void f(int n)
//{
// if(n==0) return ; //종료조건
// printf("%d ",n);
// f(n-1); //재귀호출
//}
//f(n) : 1부터 n까지 출력
// : 1 부터 n-1까지 출력 -> n 출력
// : f(n-1) -> n출력
//
//void f(int n)
//{
// if(n==0) return ;
// f(n-1);
// printf("%d ", n);
//}
//
//int main()
//{
// int n;
// scanf("%d",&n);
// f(n);
// return 0;
//}
// f(a,b) : a부터 b까지 출력 (a<=b)
/*
#include <stdio.h>
void f(int a, int b)
{
if(a > b) return;
f(a, b-1);
printf("%d", b);
}
int main()
{
int a, b;
scanf("%d %d",&a, &b);
f(a, b);
return 0;
}
*/
/*
#include <stdio.h>
void f(int n)
{
if(n==0) return;
f(n-1);
printf("%d\n", n);
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
*/
/*
#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);
return 0;
}
void f(int a, int b)
{
if(a > b) return;
f(a, b-1);
if(b%2==1)
printf("%d ", b);
}
*/
/*
#include <stdio.h>
//f(n) : return f(n-1) + n;
int f(int n)
{
if(n==0) return 0;
return f(n-1) + n;
}
int main()
{
int n;
scanf("%d",&n);
printf("%d", f(n));
return 0;
}
*/
/*
#include <stdio.h>
//f(n) : return f(n-1) + n;
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;
}
첫 번째 수와 두 번째 수는 모두 1이고
세 번째 수부터는 이전의 두 수를 더하여 나타낸다.
f(n)
f(1) return 1
f(2) return 1;
f(3) return f(2)+f(1);
...
f(n) return f(n-2)+f(n-1);
*/
/*
#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>
//long long int f(int n)
//{
//
// if(n==1 || n==0) return n%2;
//
// return f(n-1)*10+(f(n-2)%2);
//}
/*
void f(int n)
{
if(n>1)
{
f(n/2);
}
printf("%d", n%2);
}
int main()
{
int n;
scanf("%d", &n);
f(n);
return 0;
}
*/
/*
#include <stdio.h>
void f1(int n)
{
if(n==0) return;
f1(n-1);
printf("*");
}
void f(int n)
{
if(n==0) return;
f(n-1);
f1(n);
printf("\n");
}
int main()
{
int n;
scanf("%d", &n);
f(n);
return 0;
}
*/