/*
1525
#include <stdio.h>
int main()
{
int arr[11][11]= {}, parr[9][3]={};
int n,i,j,x,y,k,b;
for(i=1; i<=10; i++)
{
for(j=1; j<=10; j++)
{
scanf("%d ", &arr[i][j]);
}
}
for(i=1; i<=10; i++)
{
for(j=1; j<=10; j++)
{
if(arr[i][j]>=1)
{
b=arr[i][j];
arr[i][j]=-2;
for(k=1; k<=b && j-k>=1; k++)
{
if(arr[i][j-k]==-1) break;
else if(arr[i][j-k]==0) arr[i][j-k]=-2;
}
for(k=1; k<=b && j+k<=10; k++)
{
if(arr[i][j+k]==-1) break;
else if(arr[i][j+k]==0) arr[i][j+k]=-2;
}
for(k=1; k<=b && i+k<=10; k++)
{
if(arr[i+k][j]==-1) break;
else if(arr[i+k][j]==0) arr[i+k][j]=-2;
}
for(k=1; k<=b && i-k>=1; k++)
{
if(arr[i-k][j]==-1) break;
else if(arr[i-k][j]==0) arr[i-k][j]=-2;
}
arr[i][j]=-2;
}
}
}
scanf("%d", &n);
for(i=1; i<=n; i++)
{
scanf("%d %d", &x,&y);
parr[i][1]=x;
parr[i][2]=y;
if(arr[x][y]==0)
{
arr[x][y]=i;
}
}
for(i=1; i<=10; i++)
{
for(j=1; j<=10; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
printf("Character Information\n");
for(i=1; i<=n; i++)
{
if (arr[parr[i][1]][parr[i][2]]==i)
{
printf("player %d survive", i);
}
else
{
printf("player %d dead", i);
}
if(i<n)
{
printf("\n");
}
else if(i==n)
{
break;
}
}
return 0;
}
*/
/*
1620*
#include <stdio.h>
int fsum(int n)
{
int sum=0,i;
while(n>0)
{
sum+=n%10;
n=n/10;
}
return sum;
}
int main()
{
int n,i,b;
scanf("%d", &n);
while(n>=10)
{
n=fsum(n);
}
printf("%d", n);
return 0;
}
*/
/*
//구조체
#include <stdio.h>
typedef struct
{
int num;
char name[50];
double grade;
}student; //semicolon**
int main()
{
student arr[50];
//a.grade=3.5;
for()
{
scanf("%d %s %lf",&arr[i].num,arr[i].name,&arr[i].grade);
}
return 0;
}
*/
/*
3016**
#include <stdio.h>
typedef struct
{
char name[10];
int fgrade;
int sgrade;
int tgrade;
}student;
int main()
{
student arr[101];
int n,i,mi=1,k=1,a=1;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%s %d %d %d", arr[i].name,&arr[i].fgrade,&arr[i].sgrade,&arr[i].tgrade);
if(arr[mi].fgrade<arr[i].fgrade)
{
mi=i;
}
}
for(i=1;i<=n;i++)
{
if(arr[i].sgrade>arr[mi].sgrade)
{
k++;
}
if(arr[i].tgrade>arr[mi].tgrade)
{
a++;
}
}
printf("%s %d %d",arr[mi].name, k,a);
return 0;
}
*/
/*
4012**
#include <stdio.h>
typedef struct
{
int score;
int grade;
}grade;
int main()
{
grade arr[201];
int n,i,j,a=0;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr[i].score);
}
for(i=1;i<=n;i++)
{
a=1;
for(j=1;j<=n;j++)
{
if(arr[i].score<arr[j].score)
{
a++;
}
}
arr[i].grade=a;
printf("%d %d\n", arr[i].score, arr[i].grade);
}
return 0;
}
*/
/*
4751***
#include <stdio.h>
typedef struct
{
int country;
int student;
int score;
}result;
int main()
{
result arr[101];
int n,i,j,m,c[3];
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d %d %d", &arr[i].country,&arr[i].student,&arr[i].score);
}
for(i=1;i<=3;i++)
{
if(i==3&&c[1]==c[2])
{
for(j=1;j<=n;j++)
{
if(arr[j].country==c[1])
{
arr[j].score=0;
}
}
}
m=1;
for(j=1;j<=n;j++)
{
if(arr[m].score<arr[j].score)
{
m=j;
}
}
printf("%d %d\n",arr[m].country,arr[m].student);
arr[m].score=0;
c[i]=arr[m].country;
}
return 0;
}
*/
/*
1441
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
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;
}
}
}
for (i = 1; i <= n; i++)
printf("%d\n", a[i]);
return 0;
}
*/
/*
1442
#include <stdio.h>
int a[10001];
int n, i, j, temp, min;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=1; i<n; i++) {
min=i;
for (j=i+1; j<=n; j++)
{
if(a[j]<a[min])
{
min=j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
return 0;
}
*/