/*#include <stdio.h>
int main()
{
double a, b, c=0;
int i;
for (i=0;i<5;i++)
{
scanf("%lf %lf", &a, &b);
c+=(b-a-1.0>0)?((b-a-1.0>4)?4.0:b-a-1.0):0;
}
c/=0.5;
c*=5000;
if (c>=150000)
{
c*=0.95;
}
else if (c<=50000)
{
c*=1.05;
}
printf("%.0lf", c);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a;
scanf("%d", &a);
if (a<=500)
{
printf("%d", 7*a/10);
}
else if (a<=1500)
{
printf("%d", 350+(a-500)*4/10);
}
else if (a<=4500)
{
printf("%d", 750+(a-1500)*15/100);
}
else if (a<=10000)
{
printf("%d", 1200+(a-4500)*1/20);
}
else
{
printf("%d", 1475+(a-10000)*1/50);
}
return 0;
}
*/
//배열 array
/*
#include <stdio.h>
int main()
{
int arr[100];
int i;
for(i=0;i<100;i++)
{
scanf("%d",&arr[i]);
}
}
*/
/*
#include <stdio.h>
int main()
{
int arr[100], i, j, a;
scanf("%d", &a);
for (i=0;i<a;i++)
{
scanf("%d", &arr[i]);
}
for (j=0;j<2;j++)
{
for (i=0;i<a;i++)
{
printf("%d\n", arr[i]);
}
}
return 0;
}
*/
/*
//gokuma
#include <stdio.h>
int main()
{
int arr[1000], i, j, a;
scanf("%d", &a);
for (i=0;i<a;i++)
{
scanf("%d", &arr[i]);
}
for (i=a-1 ;i>=0;i--)
{
printf("%d ", arr[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int arr[11], i, a;
for (i=1;i<=10;i++)
{
scanf("%d", &arr[i]);
}
scanf("%d", &a);
printf("%d", arr[a]);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, arr[24]={}, a;
scanf("%d", &a);
for (i=0;i<a;i++)
{
scanf("%d", &arr[i]);
}
}
*/
/*
#include <stdio.h>
int main ()
{
int arr[1000], a, i, j, k;
scanf("%d", &a);
for (i=0; i<a; i++)
{
scanf("%d", &arr[i]);
}
for (k=0; k<a; k++)
{
printf("%d: ", k+1);
for (j=0; j<a; j++)
{
if (k!=j)
{
if (arr[k]<arr[j])
{
printf("< ");
}
else if (arr[k]>arr[j])
{
printf("> ");
}
else
{
printf("= ");
}
}
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, arr[50], i, j, k, b;
scanf("%d", &a);
for (i=0; i<a; i++)
{
arr[i]=i+1;
}
for (j=0; j<a-1; j++)
{
scanf("%d", &b);
arr[b-1]=0;
}
for (k=0; k<a; k++)
{
if (arr[k]!=0)
{
printf("%d", arr[k]);
}
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, a, arr[1000];
scanf("%d", &a);
for(i=0; i < a; i++)
{
scanf("%d", &arr[i]);
}
for(i=0; i < a; i++)
{
for(j = i; j < i+a; j++)
{
printf("%d ", arr[j%(a)]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int main()7
{
int i, j, k, arr[10000], a = 24;
scanf("%d", &k);
for(i=0; i<k; i++)
{
scanf("%d", &arr[i]);
if(a > arr[i])
{7
a=arr[i];
}
}
printf("%d", a);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i, j, k, a, b, arr[24]={0};
scanf("%d", &a);
for (i=1;i<=a;i++)
{
scanf("%d", &b);
arr[b]+=1;
}
for (j=1;j<24;j++)
{
printf("%d ", arr[j]);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a, b, c, d, i, k;
int arr[10000001]={0};
scanf("%d", &a);
for (i=0;i<a;i++)
{
scanf("%d", &b);
arr[b]=1;
}
scanf("%d", &c);
for (k=0;k<c;k++)
{
scanf("%d", &d);
printf("%d ", arr[d]);
}
return 0;
}
*/