/*
#include <stdio.h>
typedef struct
{
int num;
int m;
}gas;
int main()
{
gas st[101],temp;
int n,a,b,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&st[i].num,&st[i].m);
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(st[j].num>st[j+1].num)
{
temp=st[j];
st[j]=st[j+1];
st[j+1]=temp;
}
}
}
for(i=1;i<=n;i++)
{
printf("%d %d\n",st[i].num,st[i].m);
}
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int n,i,j,temp,c=0;;
int a[1001];
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
if(n==2)
{
if(a[1]<a[2])
{
printf("0");
return 0;
}
else
{
printf("1");
return 0;
}
}
for(i=1;i<n;i++)
{
c=0;
for(j=1;j<=n-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
c++;
}
}
if(c==0)
{
printf("%d",i-1);
return 0;
}
}
}
*/
/*
#include <stdio.h>
typedef struct
{
char name[10];
int g;
} student;
int main()
{
student st[101],temp;
int n,m,i,j;
scanf("%d %d ",&n,&m);
for(i=1; i<=n; i++)
{
scanf("%s %d",st[i].name,&st[i].g);
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(st[j].g<st[j+1].g)
{
temp=st[j];
st[j]=st[j+1];
st[j+1]=temp;
}
}
}
for(j=1; j<=m; j++)
{
printf("%s\n",st[j].name);
}
return 0;
}
*/
/*
#include <stdio.h>
int a[100001];
void swap(int pivot, int high)
{
int temp;
temp=a[pivot];
a[pivot]=a[high];
a[high]=temp;
return ;
}
void quick_sort(int s, int e)
{
int pivot=s, low=s, high=e+1;
if(s>=e) return ;
do
{
do
{
low++;
}while(a[pivot]>a[low]);
do
{
high--;
}while(a[pivot]<a[high]);
if(low<high)
{
swap(low,high);
}
}while(low<high);
swap(pivot,high);
quick_sort(s,high-1);
quick_sort(high+1,e);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
quick_sort(1,n);
for(i=1;i<=n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
char name[100];
int ss;
} s;
int main()
{
s st[101],temp;
int n,i,j,y,m,d;
scanf("%d ",&n);
for(i=1; i<=n; i++)
{
scanf("%s %d %d %d",st[i].name,&y,&m,&d);
st[i].ss=y*10000+m*100+d;
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(st[j].ss>st[j+1].ss)
{
temp=st[j];
st[j]=st[j+1];
st[j+1]=temp;
}
else if(st[j].ss==st[j+1].ss)
{
if(strcmp(st[j].name,st[j+1].name)>0)
{
temp=st[j];
st[j]=st[j+1];
st[j+1]=temp;
}
}
}
}
for(i=1; i<=n; i++)
{
printf("%s\n",st[i].name);
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
int nn;
int g;
int in;
} math;
int main()
{
math st[1001],temp;
int m,n,i,j;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d %d",&st[i].g,&st[i].in);
st[i].nn=i;
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(st[j].g<st[j+1].g)
{
temp=st[j];
st[j]=st[j+1];
st[j+1]=temp;
}
else if(st[j].g==st[j+1].g)
{
if(st[j].in<st[j+1].in)
{
temp=st[j];
st[j]=st[j+1];
st[j+1]=temp;
}
}
}
}
for(i=1;i<=n;i++)
{
printf("%d %d %d\n",st[i].nn,st[i].g,st[i].in);
}
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
char name[10];
int g;
}student;
int main()
{
student st[51],temp;
int n,i,j;
scanf("%d ",&n);
for(i=1;i<=n;i++)
{
scanf("%s %d",st[i].name,&st[i].g);
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(st[j].g>st[j+1].g)
{
temp=st[j];
st[j]=st[j+1];
st[j+1]=temp;
}
}
}
printf("%s",st[n-2].name);
return 0;
}
*/
/*
#include <stdio.h>
int main()
{
int a[8];
int i,j,temp;
for(i=1;i<=7;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<7;i++)
{
for(j=1;j<=7-i;j++)
{
if(a[j]<a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=1;i<=2;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
*/