/*
#include <stdio.h>
#include <stdlib.h>
typedef struct{
char name[20];
int s;
}stu;
int compare(stu* pa,stu* pb){
if(pa->s > pb->s) return -1;
else if(pa->s==pb->s) return 0;
else return 1;
}
int main()
{
int n,i;
stu a[51]={};
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%s %d",&a[i].name,&a[i].s);
qsort(a,n,sizeof(stu),compare);
printf("%s",a[2].name);
return 0;
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
int compare(int* pa,int* pb){
if(*pa>*pb) return 1;
else if(*pa==*pb) return 0;
else return -1;
}
int main()
{
int n,i,a,b,arr[2001]={};
scanf("%d %d",&a,&b);
n=a+b;
for(i=0;i<n;i++) scanf("%d",&arr[i]);
qsort(arr,n,sizeof(int),compare);
for(i=0;i<n;i++) printf("%d ",arr[i]);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int i,j,k;
for(i=1;i<10;i++){
for(j=0;j<10;j++){
for(k=1;k<10;k++){
if(90*i+9*j==10*k){
printf("%d%d%d-%d%d=%d%d\n",i,j,k,i,j,k,k);
}
}
}
}
return 0;
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
int arr[25][2500]={};
int main()
{
int i,j,a,b,l=1,d=0;
scanf("%d %d",&a,&b);
arr[1][0]=1;
for(i=2;i<=b;i++){
d=0;
l=1;
for(j=0;arr[i-1][(j-1)/2]!=0;j++){
if(j>0&&arr[i-1][j]==arr[i-1][j-1]) {
l++;
continue;
}
else if(j==0){
arr[i][j]=arr[i-1][j];
continue;
}
else{
arr[i][++d]=l;
l=1;
arr[i][++d]=arr[i-1][j];
continue;
}
}
}
for(i=a;i<=b;i++){
for(j=0;arr[i][j]!=0;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
double f(long long int n){
double a=0,b=n,c,d;
double k=0.000000001;
while(b-a>k){
c=(a+b)/2;
if(c*c>n) b=c;
else {
a=c;
d=c;
}
}
return d;
}
int main()
{
int t,i;
long long int n;
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%lld",&n);
printf("%.8lf\n",f(n));
}
return 0;
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
int s[15001]={};
typedef struct{
char nu[8];
int k;
}num;
int compare(num* pa,num* pb){
if(pa->k>pb->k) return -1;
else if(pa->k==pb->k) return 0;
else return 1;
}
int main()
{
int n,i,j,a;
num arr[15001]={},t;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",arr[i].nu);
a=strlen(arr[i].nu);
arr[i].k=0;
for(j=0;j<a;j++){
if(arr[i].nu[j]>64) arr[i].k+=(arr[i].nu[j]-55);
else arr[i].k+=(arr[i].nu[j]-48);
if(j!=a-1) arr[i].k*=30;
}
}
qsort(arr,n,sizeof(num),compare);
for(i=0;i<n;i++) printf("%s ",arr[i].nu);
return 0;
}
*/
/*
//기억력 테스트
#include <stdio.h>
int main()
{
int n,m,i,j,k,arr[2002]={},a,b,s;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++){
scanf("%d",&k);
arr[k+1000]++;
}
for(i=0;i<m;i++) {
s=0;
scanf("%d %d",&a,&b);
printf("%d\n",s);
}
return 0;
}*//*
//기억력 테스트2
#include <stdio.h>
int arr,s[100002]={};
int main()
{
int n,m,i,a,b,sum;
scanf("%d %d",&n,&m);
for(i=0;i<n;i++) {
scanf("%d",&arr);
s[i+1]=s[i]+arr;
}
for(i=0;i<m;i++){
scanf("%d %d",&a,&b);
sum=s[b]-s[a-1];
printf("%d\n",sum);
}
return 0;
}
*/
/*
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
char na[100];
int y,m,d;
int t;
}sc;
int compare(sc* pa,sc* pb){
if(pa->t > pb->t) return 1;
else if(pa->t==pb->t){
return compare1(pa,pb);
}
else return -1;
}
int compare1(sc* pa,sc* pb){
int l=strlen(pa->na);
for(int i=0;i<l;i++){
if(pa->na[i]> pb->na[i]) return 1;
else if(pa->na[i]<pb->na[i]) return -1;
}
return 0;
}
int main()
{
int n,i;
sc a[101]={};
scanf("%d\n",&n);
for(i=0;i<n;i++){
scanf("%s %d %d %d",a[i].na,&a[i].y,&a[i].m,&a[i].d);
a[i].t=10000*a[i].y+100*a[i].m+a[i].d;
}
qsort(a,n,sizeof(sc),compare);
for(i=0;i<n;i++){
printf("%s\n",a[i].na);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j,a,b,k;
scanf("%d %d",&a,&b);
for(i=a;i<=b;i++){
k=0;
for(j=2;j<i;j++){
if(i%j==0) {
k=1;
break;
}
}
if(k==0) printf("%d ",i);
}
return 0;
}
*/