/*
#include <stdio.h>
typedef struct
{
int num,gas;
}a;
int main()
{
int b;
a n[101];
}*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp, key;
int main()
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=2; i<=n; i++)
{
key=a[i];
for(j=i-1; j>=1 && a[j]>key; j--)
{
a[j+1]=a[j];
}
a[j+1]=key;
}
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
int num,gas;
} a;
int main()
{
int b,i,j;
a n[101],tp;
scanf("%d",&b);
for (i=1; i<=b; i++)
scanf("%d %d", &n[i].num,&n[i].gas);
for(i=1; i<b; i++)
{
for(j=1; j<=b-i; j++)
{
if(n[j].num>n[j+1].num)
{
tp=n[j];
n[j]=n[j+1];
n[j+1]=tp;
}
}
}
for(i=1; i<=b; i++)
printf("%d %d\n",n[i].num,n[i].gas);
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
int num,math,jungbo;
} student;
int main()
{
int n,i,j;
student tp,a[1001];
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d %d",&a[i].math,&a[i].jungbo);
a[i].num=i;
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(a[j].math<a[j+1].math)
{
tp=a[j];
a[j]=a[j+1];
a[j+1]=tp;
}
else if(a[j].math==a[j+1].math)
{
if(a[j].jungbo<a[j+1].jungbo)
{
tp=a[j];
a[j]=a[j+1];
a[j+1]=tp;
}
else if(a[j].jungbo==a[j+1].jungbo)
{
if(a[j].num>a[j+1].num)
{
tp=a[j];
a[j]=a[j+1];
a[j+1]=tp;
}
}
}
}
}
for(i=1; i<=n; i++)
printf("%d %d %d\n",a[i].num,a[i].math,a[i].jungbo);
return 0;
}
*/
/*
#include <stdio.h>
typedef struct
{
char name[11];
int year,month,day;
} memo;
int main()
{
int i,j,n;
memo a[101],tp;
scanf("%d",&n);
for(i=1; i<=n; i++)
scanf("%s %d %d %d",a[i].name,&a[i].year,&a[i].month,&a[i].day);
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if(a[j].year>a[j+1].year)
{
tp=a[j];
a[j]=a[j+1];
a[j+1]=tp;
}
else if(a[j].year==a[j+1].year)
{
if(a[j].month>a[j+1].month)
{
tp=a[j];
a[j]=a[j+1];
a[j+1]=tp;
}
else if(a[j].month==a[j+1].month)
{
if(a[j].day>a[j+1].day)
{
tp=a[j];
a[j]=a[j+1];
a[j+1]=tp;
}
else if(a[j].day==a[j+1].day)
{
if(strcmp(a[j].name,a[j+1].name)>0)
{
tp=a[j];
a[j]=a[j+1];
a[j+1]=tp;
}
}
}
}
}
}
for(i=1; i<=n; i++)
printf("%s\n",a[i].name);
return 0;
}
*/
/*
#include <stdio.h>
int stack[100];
int top=-1;
void push(int data)
{
top++;
stack[top]=data;
}
int pop()
{
return stack[top--];
}
int main()
{
push(1);
push(2);
push(3);
push(4);
while(top!=-1) //스택에 들어있는 것 모두 pop해서 출력하기
{
printf("%d\n",pop());
}
}
*/
/*
#include <stdio.h>
char stack[100];
int top=-1;
void push(char data)
{
top++;
stack[top]=data;
}
char pop()
{
return stack[top--];
}
int main()
{
char str[11];
scanf("%s",str);
for(int i=0; i<strlen(str); i++)
{
push(str[i]);
}
while(top!=-1)
{
printf("%c",pop());
}
return 0;
}
*/
/*
#include <stdio.h>
char stack[200];
int top=-1;
void push(char data)
{
top++;
stack[top]=data;
}
char pop()
{
return stack[top--];
}
int main()
{
char str[201];
int n;
scanf("%d",&n);
scanf("%s",str);
while(n>0)
{
n--;
push(str[n]);
}
while(top!=-1)
{
printf("%c",pop());
if((top+1)%3==0&&top!=-1)
{
printf(",");
}
}
return 0;
}
*/