/*
#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*
#include <stdio.h>
int n;
long long int d[110];
long long int f()
{
long long int i,min=d[1];
for(i=1;i<=n;i++){
if(min>d[i]){
min=d[i];
}
}
return min;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%lld", &d[i]);
printf("%lld", f());
return 0;
}
*/
/*
#include <stdio.h>
int n;
long long int i,a=1;
long long int f()
{
for(i=1;i<=n;i++){
a*=i;
}
return a;
}
int main()
{
scanf("%d", &n);
printf("%lld\n", f(n));
}
*/
/*
#include <stdio.h>
int n, m;
int min()
{
if(n<m){
return n;
}
else{
return m;
}
}
int main()
{
scanf("%d%d", &n, &m);
printf("%d\n", min(n, m));
}
*/
/*
#include <stdio.h>
int n, a, b, d[1010];
long long int subsetsum(int a, int b)
{
long long int i,sum=0;
for(i=a;i<=b;i++){
sum+=d[i];
}
return sum;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
scanf("%d%d", &a, &b);
printf("%lld\n", subsetsum(a, b));
}
*/
/*
#include <stdio.h>
int n, k, d[1010];
int upper_bound(int k)
{
int i;
for(i=1;i<=n;i++){
if(k<d[i])
{
return i;
}
if(i==n)
{
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>
long long int n;
long long int f()
{
long long int m=0;
while(1)
{
m=m*10+n%10;
n/=10;
if(n==0)
return m;
}
}
int main()
{
scanf("%lld", &n);
printf("%lld\n", f(n));
}
*/
/*
#include <stdio.h>
int n;
char grade(int k)
{
if(k>=90){
return 'A';
}
else if(90>k&& k>=80){
return 'B';
}
else if(80>k&&k>=70){
return 'C';
}
else if(70>k&&k>=60){
return 'D';
}
else {
return 'F';
}
}
int main()
{
scanf("%d", &n);
printf("%c", grade(n));
return 0;
}
*/
/*
#include <stdio.h>
int n, d[100010], k;
int f(int k)
{
int i;
for(i=1;i<=n;i++){
if(d[i]==k){
return i;
}
if(i==n)
return -1;
}
}
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &d[i]);
scanf("%d", &k);
printf("%d\n", f(k));
}
*/
/*
#include <stdio.h>
int n, k, d[1010];
int lower_bound(int k)
{
int i;
for(i=1;i<=n;i++){
if(k<=d[i]){
return i;
}
if(i==n){
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", lower_bound(k));
}
*/