//#include <stdio.h>
//int main()
//{
// int a[50][3]={};
// int n, i, j, x, y;
// scanf("%d",&n);
// for(i=0;i<n;i++)
// scanf("%d %d",&a[i][0],&a[i][1]);
// int cnt;
// for(i=0;i<n;i++){
// cnt=0;
// for(j=0;j<n;j++){
// if(a[i][0]<a[j][0] && a[i][1]<a[j][1]){
// cnt++;
// }
// }
// printf("%d ",cnt+1);
// }
//
// return 0;
//}
//4775 : 점모으기
//1. 최빈행, 열로 옮긴다.
//2. 최대,최소의 평균으로 옮긴다.
/*
#include <stdio.h>
int x[10001]={}, y[10001]={};
int p[100001][2]={};
int main()
{
int n, m, a, b, mx, my;
int max_x=1, min_x=10000, max_y=1, min_y=10000, sum=0, sum1=0;
scanf("%d %d",&n, &m);
for(int i=0;i<m;i++){
scanf("%d %d",&a, &b);
p[i][0]=a;p[i][1]=b;
x[a]++; y[b]++;
if(max_x<a) max_x=a;
if(min_x>a) min_x=a;
if(max_y<b) max_y=b;
if(min_y>b) min_y=b;
}
for(int i=1;i<=n;i++){
if(x[mx]<=x[i]) mx=i;
if(y[my]<=y[i]) my=i;
}
//printf("%d %d", mx, my);
for(int i=0;i<m;i++){
sum1+=abs(p[i][0]-mx)+abs(p[i][1]-my);
}
mx=(max_x+min_x)/2;
my=(max_y+min_y)/2;
for(int i=0;i<m;i++){
sum+=abs(p[i][0]-mx)+abs(p[i][1]-my);
}
printf("%d",sum<sum1?sum:sum1);
return 0;
}
*/
/*
#include<stdio.h>
#include<string.h>
int main()
{
char s[1001]= {};
int n, i;
scanf("%s",s);
n=strlen(s);
for(i=0; i<n; i++)
{
if(s[i]<91&&s[i]>64)
{
printf("%c",s[i]+32);
}
else if(s[i]>96&&s[i]<123)
{
printf("%c",s[i]-32);
}
else
{
printf("%c",s[i]);
}
}
return 0;
}
*/
/*
#include<string.h>
#include<stdio.h>
int main()
{
int n, k1, k2, k3;
char s1[21]={}, s2[21]={}, s3[21]={};
scanf("%s",s1);
scanf("%s",s2);
scanf("%s",s3);
k1=strlen(s1);
k2=strlen(s2);
k3=strlen(s3);
if(s1[k1-1]==s2[0]&&s2[k2-1]==s3[0]&s3[k3-1]==s1[0])
{
printf("good");
}
else
{
printf("bad");
}
return 0;
}
*/
/*
#include<stdio.h>
#include<string.h>
int main()
{
int n, i, j;
char s[100]={};
scanf("%d",&n);
if(n==0)
{
printf("0");
}
for(i=0;n!=0;i++)
{
s[i]=n%2+'0';
n/=2;
}
s[i]=NULL;
j=strlen(s);
for(i=j-1;i>=0;i--)
{
printf("%c",s[i]);
}
return 0;
}
a=k++; a=k; k++;
a=++k; k++; a=k;
1- 1,3,5,7
2- 1,3 // 5 ,
#include<stdio.h>
int main()
{
int arr[5][6]={};
int i, j, k=1;
for(j=1;j<=4;j++){
for(i=1;i<=3;i++){
arr[i][j]=k++;
}
}
for(i=1;i<=3;i++){
for(j=1;j<=4;j++){
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int arr[100][100]={};
int i, j, n, k=1;
scanf("%d", &n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
arr[i][j]=k++;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int arr[100][100]={};
int i, j, n, k=1;
scanf("%d", &n);
for(j=0;j<n;j++)
{
for(i=0;i<n;i++)
{
arr[i][j]=k++;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int arr[100][100]={};
int i, j, n, m, k=1;
scanf("%d %d", &n, &m);
for(i=n-1;i>=0;i--)
{
for(j=m-1;j>=0;j--)
{
arr[i][j]=k++;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int arr[100][100]={};
int i, j, n, m, k=1;
scanf("%d %d", &n, &m);
for(j=m-1;j>=0;j--)
{
for(i=n-1;i>=0;i--)
{
arr[i][j]=k++;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int arr[100][100]= {};
int i, j, n, k=1;
scanf("%d", &n);
for(j=0; j<n; j++)
{
if(j%2==0)
{
for(i=0; i<n; i++)
{
arr[i][j]=k++;
}
}
else
{
for(i=n-1; i>=0; i--)
{
arr[i][j]=k++;
}
}
}
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int arr[100][100]= {};
int i, j, n, m, k=1;
scanf("%d %d", &n, &m);
for(i=0; i<m; i++)
{
if(i%2==0)
{
for(j=n-1; j>=0; j--)
{
arr[i][j]=k++;
}
}
else
{
for(j=0; j<n; j++)
{
arr[i][j]=k++;
}
}
}
for(j=0; j<n; j++)
{
for(i=m-1; i>=0; i--)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int n, m, i, j, k=1;
int arr[100][100]={};
scanf("%d", &n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i][0]);
}
for(i=1;i<n;i++)
{
for(j=1;j<=i;j++)
{
arr[i][j]=arr[i][j-1]-arr[i-1][j-1];
}
}
for(i=0;i<n;i++)
{
for(j=0;j<=i;j++)
{
printf("%d ",arr[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include<stdio.h>
int main()
{
int n, m, i, j;
int arr[100][100]= {};
for(i=0; i<11; i++)
{
for(j=0; j<10; j++)
{
scanf("%d",&arr[i][j]);
}
}
for(j=0; j<10; j++)
{
if(arr[10][j]==1)
{
for(i;; i--)
{
}
}
}
return 0;
}
*/