/*#include <stdio.h>
int main()
{
int a, b, n, max;
scanf("%d %d",&a , &b);
n=a>b?b:a;
for(int i=1;i<=n;i++)
{
if(a%i==0 && b%i==0)
{
max=i;
}
}
printf("%d", max);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, cnt=0, max, el;
scanf("%d", &n);
for(int i=1;i<n-1;i++)
{
for(int j=1;j<n-1;j++)
{
for(int k=1;k<n-1;k++)
{
if(i>j && i>k)
{
max=i;
el=j+k;
}
else if(j>i && j>k)
{
max=j;
el=i+k;
}
else if(k>i && k>j)
{
max=k;
el=i+j;
}
else if(k==i && i==j)
{
max=i;
el=k+j;
}
if(i+j+k==n && max < el)
{
cnt++;
}
}
}
}
printf("%d", cnt);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, k, arr[100000], flag=0;
scanf("%d %d", &n, &k);
for(int i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
for(int i=0;i<n;i++)
{
if(arr[i]>=k && flag==0)
{
printf("%d", i+1);
flag=1;
}
}
if(flag==0)
{
printf("%d", n+1);
}
return 0;
}
1, 2, 3, 5, 8, 13,
*/
/*
#include <stdio.h>
int memo[10001];
int f(int n)
{
if(n==1) return memo[1]=1;
else if(n==2) return memo[2]=2;
if(memo[n]!=0) {
return memo[n];
}
return memo[n]=(f(n-1)+f(n-2))%100000007;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n));
return 0;
}
1, 3, 5, 11, 21
*/
/*
#include <stdio.h>
int memo[10001];
int f(int n)
{
if(memo[n]!=0){
return memo[n];
}
if(n==1) return memo[1]=1;
else if(n==2) return memo[2]=3;
return memo[n]=(f(n-1)+f(n-2)*2)%100007;
}
int main()
{
int n;
scanf("%d", &n);
printf("%d", f(n));
return 0;
}
1, 5, 11, 33,
*/
/*
#include <stdio.h>
int main()
{
int cnt=0, a, b, max=0;
for(int i=0;i<4;i++)
{
scanf("%d %d", &a, &b);
cnt-=a;
if(cnt<=10000)
cnt+=b;
if(max<cnt)
max=cnt;
}
printf("%d", max);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, max=0, cnt=0;
for(int i=0;i<10;i++)
{
scanf("%d %d", &a, &b);
cnt-=a;
if(cnt<10000)
cnt+=b;
if(cnt>max)
max=cnt;
}
printf("%d", max);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int A, B, C, D;
scanf("%d %d %d", &A, &B, &C);
scanf("%d", &D);
C+=D;
B+=C/60;
C%=60;
A+=B/60;
B%=60;
A%=24;
printf("%d %d %d", A, B, C);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n, min=1001, max=0, score;
scanf("%d", &n);
for(int i=0;i<n;i++)
{
scanf("%d", &score);
if(min>score)
min=score;
if(max<score)
max=score;
}
printf("%d", max-min);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, sum=0;
for(int i=0;i<5;i++){
scanf("%d", &a);
sum+=a*a;
}
sum%=10;
printf("%d", sum);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, c, d, sum[3]={};
for(int i=0;i<3;i++){
scanf("%d %d %d %d", &a, &b, &c, &d);
sum[i]=a+b+c+d;
}
for(int i=0;i<3;i++){
if(sum[i]==3)
printf("A\n");
else if(sum[i]==2)
printf("B\n");
else if(sum[i]==1)
printf("C\n");
else if(sum[i]==0)
printf("D\n");
else if(sum[i]==4)
printf("E\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int N, K, arr[10000], j, flag=0;
scanf("%d %d", &N, &K);
j=0;
for(int i=1;i<=N;i++)
{
if(N%i==0)
{
arr[j]=i;
j++;
flag=1;
}
}
if(j>K)
printf("%d", arr[K-1]);
else
printf("0");
return 0;
}
*/