/*#include <stdio.h>
#include <stdlib.h>
int main()
{
printf("Hello world!\n");
return 0;
}
*/
/*#include <stdio.h>
int main()
{
int arr[1001]= {};
int n,i,j,k,tmp,sum=0;
scanf("%d",&n);
for (i=1; i<=n; i++)
{
scanf("%d",&arr[i]);
}
for(i=1; i<n; i++)
{
for(j=1; j<n; j++)
{
if(arr[j]>arr[j+1])
{
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
for(k=1; k<n; k++)
{
if(arr[k]>arr[k+1])
{
break;
}
}
if(k==n)
{
printf("%d",sum+1);
return 0;
}
sum++;
}
return 0;
}
*/
//#include<stdio.h>
//int main()
//{
// int n,arr[1001][3]= {},tmp,i,j;
// scanf("%d",&n);
// for(i=0; i<n; i++)
// {
// for(j=0; j<2; j++)
// {
// scanf("%d",&arr[i][j]);
// }
// }
// for(i=0; i<n; i++)
// {
// for(j=0; j<2; j++)
// {
// if(arr[i][1]>arr[i+1][1])
// {
// tmp=arr[i][1];
// arr[i][1]=arr[i+1][1];
// arr[i+1][1]=tmp;
// }
// }
// }
// for(i=0; i<n; i++)
// {
// for(j=0; j<2; j++)
// {
// if(arr[j][1]>arr[j+1][1])
// {
// tmp=arr[j][1];
// arr[j][1]=arr[j+1][1];
// arr[j+1][1]=tmp;
// }
// }
// }
// for(i=0; i<n; i++)
// {
// for(j=0; j<2; j++)
// {
// printf("%d ",arr[i][j]);
// }
// printf("\n");
// }
// return 0;
//}
/*#include<stdio.h>
struct node
{
int x, y, number;
};
int main()
{
struct node data[1005] = {0};
struct node temp;
int i, j, n;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d %d", &data[i].x, &data[i].y);
data[i].number = i+1;
}
for(i=0; i<n; i++)
{
for(j=0; j<n-1; j++)
{
if(data[j].x < data[j+1].x)
{
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
if(data[j].y<data[j+1].y&&data[j].x==data[j+1].x)
{
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
}
for(i=0; i<n; i++)
{
printf("%d %d %d\n", data[i].number, data[i].x, data[i].y);
}
}*/
/*#include<stdio.h>
int p,left,right,arr[20]= {},i,n;
int L(int x,int y)
{
for(i=0;i<n;i++)
{
arr[x++];
if(arr[x]>p)
{
break;
}
}
if(x==y)
{
p=arr[x];
L(p+1,arr[n]);
}
}
int R(int x,int y)
{
for(i=n;i>0;i--)
{
arr[y--];
if(arr[y]>p)
{
break;
}
}
if(x==y)
{
p=arr[y];
R(p+1,arr[n]);
}
}
int main()
{
scanf("%d",&n);
for(i=0; i<n; i++)
{
scanf("%d",&arr[i]);
}
p=arr[0];
left=arr[1];
right=arr[n];
L(left,right);
R(left,right);
for(i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
}
*/
/*#include<stdio.h>
int arr[100001]={},begin,start,pivot,tmp,n;
int partition(int begin,int end)
{
pivot=(begin+end)/2;
while(begin<end)
{
while(arr[begin]<arr[pivot]&&begin<end)
{
begin++;
}
while(arr[end]>=arr[pivot]&&begin<end)
{
end--;
}
if(begin<end)
{
tmp=arr[begin];
arr[begin]=arr[end];
arr[end]=tmp;
if(begin==pivot)
{
pivot=end;
}
}
}
tmp=arr[pivot];
arr[pivot]=arr[end];
arr[end]=tmp;
return end;
}
int quickSort(int begin,int end)
{
int p;
if(begin<end)
{
p=partition(begin,end);
quickSort(begin,p-1);
quickSort(p+1,end);
}
return 0;
}
int main()
{
int i;
scanf("%d",&n);
for(i=0; i<n; i++){
scanf("%d", &arr[i]);
}
quickSort(0,n-1);
for(i=0; i<n; i++) {
printf("%d\n", arr[i]);
}
return 0;
}*/
/*#include <stdio.h>
int main()
{
int n,x,max=0,i,j,arr[100000]={};
scanf("%d",&n);
for (i=0;i<n;i++)
{
scanf("%d",&x);
arr[x]++;
if (x>max)
{
max=x;
}
}
for (i=0;i<=max;i++)
{
for(j=0;j<arr[i];j++)
{
printf("%d ",i);
}
}
return 0;
}
*/