//#include <stdio.h>
//
//struct a
//{
// char b[20];
// int c;
//};
//int main()
//{
// int n, i, j;
// scanf("%d", &n);
// struct a stu[51],temp;
// for(i=1;i<=n;i++)
// {
// scanf("%s %d", stu[i].b, &stu[i].c);
// }
// for(i=1;i<n;i++)
// {
// for(j=1;j<n;j++)
// {
// if(stu[j].c<stu[j+1].c)
// {
// temp=stu[j];
// stu[j]=stu[j+1];
// stu[j+1]=temp;
// }
// }
// }
//
// printf("%s", stu[3].b);
//
// return 0;
//}
//#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>
//
//
//void swap(int arr[], int a, int b)
//{
// int temp;
// temp = arr[a];
// arr[a] = arr[b];
// arr[b] = temp;
//}
//
//int part(int arr[], int a, int b)
//{
// int pivot = arr[a];
// int low=a+1, high=b;
// while(low<=high)
// {
// while(pivot>=arr[low] &&low<=b)
// {
// low++;
// }
// while(pivot<=arr[high] &&high>=(a+1))
// {
// high--;
// }
//
// if(low<=high)
// {
// swap(arr,low,high);
// }
// }
// swap(arr,a,high);
// return high;
//}
//
//
//
//void quick_sort(int arr[],int a, int b)
//{
// if(a<=b)
// {
// int pivot = part(arr,a,b);
// quick_sort(arr,a,pivot-1);
// quick_sort(arr,pivot+1,b);
// }
//}
//
//
//
//int main()
//{
// int arr[100000],i,n;
// scanf("%d",&n);
// for(i = 0; i<n;i++)
// {
// scanf("%d",&arr[i]);
// }
// quick_sort(arr,0,n-1);
//
// for(i = 0; i<n; i++)
// {
// printf("%d\n",arr[i]);
// }
//
//}
//#include <stdio.h>
//
//int main()
//{
// int i,j, a[7], temp;
// for(i=1;i<=7;i++)
// {
// scanf("%d", &a[i]);
// }
// for(i=1;i<7;i++)
// {
// for(j=1;j<7;j++)
// {
// if(a[j]<a[j+1])
// {
// temp=a[j];
// a[j]=a[j+1];
// a[j+1]=temp;
// }
// }
// }
// printf("%d %d", a[1], a[2]);
//}
//#include <stdio.h>
//struct a
//{
// int b, c, d;
//};
//
//int main()
//{
// struct a stu[1001], temp;
// int n, i, j;
//
// scanf("%d",&n);
//
// for(i=1;i<=n;i++)
// {
// scanf("%d %d", &stu[i].c, &stu[i].d);
// stu[i].b=i;
// }
//
// for(i=1;i<n;i++)
// {
// for(j=1;j<n;j++)
// {
// if(stu[j].c<stu[j+1].c)
// {
// temp=stu[j];
// stu[j]=stu[j+1];
// stu[j+1]=temp;
// }
// else if(stu[j].c==stu[j+1].c)
// {
// if(stu[j].d<stu[j+1].d)
// {
// temp=stu[j];
// stu[j]=stu[j+1];
// stu[j+1]=temp;
// }
// else if(stu[j].d==stu[j+1].d)
// {
// if(stu[j].b>stu[j+1].b)
// {
// temp=stu[j];
// stu[j]=stu[j+1];
// stu[j+1]=temp;
// }
// }
// }
// }
// }
//
// for(i=1;i<=n;i++)
// {
// printf("%d %d %d\n", stu[i].b, stu[i].c, stu[i].d);
//
// }
// return 0;
//
//
//}