//1 星期几
// int main()
// {
// int n;
// cin >> n;
// switch(n)
// {
// case 1:
// cout <<"Monday"<<endl;
// break;
// case 2:
// cout <<"Tuesday"<<endl;
// break;
// case 3:
// cout <<"Wednesday"<<endl;
// braek;
// case 4:
// cout <<"Thursday"<<endl;
// break;
// case 5:
// cout <<"Friday"<<endl;
// break;
// case 6:
// cout <<"Saturday"<<endl;
// break;
// case 7:
// cout <<"Sunday"<<endl;
// break;
// default:
// cout <<"N/A"<<endl;
// break;
// }
// return 0;
// }
//2 会员
// int main()
// {
// char n;
// int m;
// cin >>n;
// cin >>m;
// switch(n)
// {
// case 'P':
// cout<<m*0.7<<endl;
// break;
// case 'G':
// cout<<m*0.8<<endl;
// break;
// case 'S':
// cout<<m*0.9<<endl;
// break;
// default:
// cout<<m*0.95<<endl;
// break;
// }
// return 0;
// }
// 3 某年某月的天数
// int main()
// {
// int x,y;
// cin >> x>>y;
// switch(y)
// {
// case 1:
// case 3:
// case 5:
// case 7:
// case 8:
// case 10:
// case 12:
// cout << 31 << endl;
// break;
// case 4:
// case 6:
// case 9:
// case 11:
// cout << 30 << endl;
// break;
// case 2:
// if (x % 4 == 0)
// {
// cout << 29 << endl;
// break;
// }
// else
// {
// cout << 28 << endl;
// break;
// }
// }
// return 0;
// }
// 4 成绩等级
// int main()
// {
// int n;
// cin >> n;
// switch(n/10)
// {
// case 9:
// case 10:
// cout << "A" << endl;
// break;
// case 7:
// case 8:
// cout << "B" << endl;
// break;
// case 6:
// cout << "C" << endl;
// break;
// default:
// cout << "D" << endl;
// break;
// }
// return 0;
// }
// 5 快递计费
// int main()
// {
// int s;
// double d,p,w,f;
// cin >> p>>w>>s;
// switch(s/250)
// {
// case 0: d = 0;break;
// case 1: d = 0.02;break;
// case 2:
// case 3: d = 0.05;break;
// case 4:
// case 5:
// case 6:
// case 7: d = 0.08;break;
// case 8:
// case 9:
// case 10:
// case 11: d = 0.1;break;
// default:
// d = 0.15;break;
// }
// f = p * w * s *(1-d);
// printf("%.2f元",f);
// return 0;
// }
// 6 开关灯
// #include<iostream>
// using namespace std;
// int main()
// {
// bool light = false;
// int n;
// cin>>n;
// if(n%2 == 0)
// {
// cout <<"关灯";
// }
// else
// {
// cout <<"开灯";
// }
// }
// 7 美美的门
// int main()
// {
// bool d1,d2,d3,d4,d5,d6,d7;
// int s = 0 ;
// d1=d2=d3=d4=d5=d6=d7=true;
// d2 = !d2;
// d4 = !d4;
// d6 = !d6;
// d3 = !d3;
// d6 = !d6;
// if(d1)s++;
// if(d2)s++;
// if(d3)s++;
// if(d4)s++;
// if(d5)s++;
// if(d6)s++;
// if(d7)s++;
// cout << s <<endl;
// return 0;
// }
// 8 开关灯2.0
// int main()
// {
// int n,m;
// bool light;
// cin >> n >>m;
// cout << 1;
// for(int i = 2 ;i <=n; i++)
// {
// light = true;
// for (int j = 1; j <= m;j++)
// {
// if (i%j == 0)
// {
// light = !light;
// }
// }
// if (light == false)
// {
// cout <<","<< i;
// }
// }
// return 0;
// }
// 9 逆序输出
// int main()
// {
// int a[10];
// for (int i=0;i<4;i++)
// {
// cin >>a[i];
// }
// cout<<a[3]<<" "<<a[2]<<" "<<a[1]<<" "<<a[0]<<endl;
// return 0;
// }
// 10.1 递归练习
// const int NUM=5;
// int fun(int n)
// {
// if(n<=NUM) return n;
// for(int i=1;i<=NUM;)
// return -1;
// }
// int main()
// {
// return 0;
// }
// 11 国王的米数
// int main(){
// long long s = 0;
// long long n = 1;
// for(int i= 1;i <= 62; i++){
// n = n * 2;
// s += n; //int最大2147483647
// }
// cout<<"米的总数"<<s<<endl;
// return 0;
// }
// 12 找质数
// int main(){
// int n,s;
// cin>>n;
// for(int i = 2;i<=n-1;i++){
// if (n%i==0)
// s +=1;
// }
// if(s>0)
// cout<<"不是质数";
// else
// cout<<"是质数";
// return 0;
// }
// 13 操场排队（韩信点兵）
// int main(){
// int x = 0;
// int yes;
// do{
// x = x + 1;
// yes = 1;
// if (x%2!=!1){
// yes = 0;
// }
// if (x%3!=!1){
// yes = 0;
// }
// if (x%4!=!1){
// yes = 0;
// }
// if (x%5!=!1){
// yes = 0;
// }
// if (x%6!=!1){
// yes = 0;
// }
// }while(yes = 0);
// return 0;
// }
// while和do while
// int main(){
// int i = 11;
// int s = 0;
// while(i<=10)
// {
// s += i;
// i++;
// }
// cout<<s;
// do{
// s += i;
// i++;
// }while (i<=10);
// cout<<s;
// }
// 14 循环专题练习1
// int main(){
// int m,n,i;
// cin>>m>>n;
// for(i=m;i<=n;i++){
// }
// }
// 14 循环专题练习2
// int main(){
// char c1,c2;
// cin>>c1>>c2;
// for(c1;c1<=c2;c1++){
// cout<< c1 <<endl;
// }
// return 0;
// }
// nnnnnnnnnnnnnnnnnnnnnnnnnnoooooooooooooooooiiiiiiiiiiiiiiii
// int main(){
// int n;
// cin>>n;
// int max1=0;
// for (int i=1;i<=n;i++){
// int fs;
// cin>>fs;
// if(max1 < fs)
// max1=fs;
// }
// cout <<max1;
// return 0;
// }
// int main(){
// int n,i=0;
// cin>>n;
// int max1=0;
// int max2=0;
// for(i;i<=n;i++){
// int man;
// cin>>man;
// if(max1<man)
// max1= man;
// if(max2>man)
// max2= man;
// }
// cout<<max1-max2;
// return 0;
// }
// int main(){
// int n;
// cin>>n;
// double fs,s=0;
// for (int i=1;i<=n;i++){
// cin >> fs;
// s +=fs;
// }
// printf("%.4f",(s/n));
// return 0;
// }
// int main(){
// int n;
// cin>>n;
// double fs,s=0;
// for (int i=1;i<=n;i++){
// cin >> fs;
// s +=fs;
// }
// cout<<s<<' ';
// printf("%.5f",(s/n));
// return 0;
// }
// int main(){
// int n,man=0;
// cin>>n;
// for(int i=1;i<=n;i++){
// if(n%i==0)
// cout<<i<<endl;
// }
// }
// int main(){
// for(int i=1000;i<=9999;i++){
// if(sqrt(i)==(int)sqrt(i)){
// int qian,bai,shi,ge;
// qian = i/1000;
// bai = (i/100)%10;
// shi = (i/10)%10;
// ge = i%10;
// if(qian==bai&&shi==ge)
// cout<<i<<endl;
// }
// }
// return 0;
// }
// int main(){
// int n,a,b,c;
// int j = 0,y = 0,t=0;
// cin >>n;
// for(int i=1;i<=n;i++){
// cin>>a>>b>>c;
// j+=a;
// y+=b;
// t+=c;
// }
// cout<<j<<" "<<y<<" "<<t<<" "<<j+y+t;
// return 0;
// }
// #include<iostream>
// using namespace std;
// int main(){
// int n,m,cnt=0;
// cin>> n>>m;
// int b[101];
// for(int i=0;i<=n-1;i++){
// cin>>b[i];
// if (b[i]==m)
// cnt+=1;
// }
// cout<<cnt;
// return 0;
// }
// int main(){
// int n,cnt=0;
// cin>>n;
// for(int i=1;i<=n;i++){
// int a;
// cin>>a;
// if(a%10-a/1000-(a/100)%10-(a/10)%10>=0)
// cnt+=1;
// }
// cout<<cnt;
// return 0;
// }
// ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// 15 大小写字母
// int main(){
// for(int i = 65;i<=90;i++){
// cout<<char(i)<<" ";
// }
// cout<<endl;
// for(char c= 'a';c<='z';c++){
// cout<<c<<" ";
// }
// return 0;
// }
// 16 从大到小
// int main(){
// int n,m;
// cin>>n>>m;
// for(m;m>=n;m--){
// cout << i<<" ";
// }
// return 0;
// }
// 17 直角三角形 1.0 & 2.0
// int main(){
// int n;
// int k = 1;
// cin >>n;
// for(int i=1;i<=n;i++){
// for(int j = 1;j<=i;j++){
// cout<<"*";
// }
// cout<<endl;
// }
// for(int i=1;i<=n;i++){
// for(int j = 1;j<=i;j++){
// cout<<k;
// k++;
// if(k>=10)
// k =0;
// }
// cout<<endl;
// }
// for(int i=1;i<=n;i++){
// for(int j = 1;j<=i;j++){
// cout<<k%10;
// k++;
// }
// cout<<endl;
// }
// return 0;
// }
// 18 财务管理
// #include<iostream>
// using namespace std;
// int main(){
// float a = 0;
// for(int i=1;i<=12;i++){
// float n;
// cin>>n;
// a += n;
// }
// cout<<'$';
// printf("%.2f",(a/12));
// return 0;
// }
// 19 数组的使用
// int main(){
// int b[5]={};
// for(int i=1;i<=5;i++){
// cin>>b[i];
// }
// for(int j=5 ;j>=1;j--)
// cout<<b[j]<<endl;
// int a[10]={};
// for(int r=1;r<=10;r++){
// cin>>a[r];
// }
// int w;
// w=a[3]+a[9];
// cout<<w<<endl;
// return 0;
// }
//幸运数
// int main(){
// int n,m;
// int flag = 1;
// cin >>n;
// for(int i=1;i<=n;i++){
// m =i;
// while(m !=0){
// if (m%10 !=4 && m%10 !=7)
// break;
// m=m/10;
// }
// if(m==0){
// if(n%i==0){
// flag = 0;
// cout<<"YES";
// }
// }
// }
// if (flag==1)cout<<"nnnnnnnnnnnnnooooooooooooo";
// return 0;
// }
// #include<iostream>
// using namespace std;
// int main(){
// int n,flag;
// int lucky[20]={};
// for (int i=0;i<=9;i++){
// cin>>lucky[i];
// }
// cin>>n;
// flag =n+30;
// int cnt=0;
// for(int j =0;j<=9;j++)
// {
// if(flag>=lucky[j]){
// cnt =cnt+1;
// }
// }
// cout<<cnt;
// return 0;
// }
// #include<iostream>
// using namespace std;
// int main(){
// int n;
// double s;
// float wuyichen[10]={28.9,32.7,45.6,78,35,86.2,27.8,43,56,65};
// for(int i=0;i<10;i++){
// cin>>n;
// s += n*wuyichen[i];
// }
// cout<<s;
// return 0;
// }
// #include<iostream>
// using namespace std;
// int main(){
// int n,x[105],y,cnt=0;
// cin>>n;
// for(int i=1;i<=n;i++){
// cin>>x[i];
// }
// cin>>y;
// for(int j=1;j<=n;j++)
// if(x[j]==y) cnt +=1;
// cout<<cnt;
// return 0;
// }
// #include<iostream>
// using namespace std;
// int main(){
// int x,n[1000];
// cin>>x;
// for (int i =1;i<=x;i++){
// cin >>n[i];
// }
// for(int j=x;j>=1;j--){
// cout<<n[j]<<" ";
// }
// return 0;
// }
// #include<iostream>
// using namespace std;
// int main(){
// for (char i='a';i<='z';i+=2){
// cout<<i<<" ";
// }
// cout<<endl;
// for (char e='z';e>='a';e-=2){
// cout<<e<<" ";
// }
// return 0;
// }
// int main(){
// int x,y;
// cin>>x>>y;
// cout<<5*x+2*y;
// return 0;
// }
// int main(){
// // int a[10];
// // for(int i=0;i<=2;i++){
// // cin>>a[i];
// // }
// // int f=0;
// // for(int j=0;j<=2;j++){
// // if(a[j]>f)
// // f=a[j];
// // }
// // cout<<f<<endl;
// // int g=2147483647;
// // for(int q=0;q<=2;q++){
// // if(a[q]<g)
// // g=a[q];
// // }
// // cout<<g;
// int a,b,c;
// cin>>a>>b>>c;
// cout<<max(max(a,b),c)<<endl;
// cout<<min(min(a,b),c)<<endl;
// return 0;
// }
// int main(){
// int a,b,c,cnt=0;
// int n[5001];
// cin>>a>>b>>c;
// for(int i=1;i<=a;i++){
// cin>>n[i];
// }
// for(int j=1;j<=a;j++){
// if(b<n[j]&&n[j]<c){
// cnt+=n[j];
// }
// }
// cout<<cnt;
// }
// 获取带空格的数
// int main(){
// char c[2147];
// cin.getline(c,2147);
// cout<<c;
// return 0;
// }
// 21点 小のman~
// int main(){
// char sp[16];
// cin>>sp;
// int total=0;
// for(int i =0;i<strlen(sp);i++){
// if(sp[i]=='A')
// total +=1;
// else if(sp[i]=='J'||sp[i]=='Q'||sp[i]=='K')
// total+=10;
// else if(sp[i]=='0')
// total+=10;
// else if(sp[i]=='1')
// continue;
// else
// total+=int(sp[i])-48;
// }
// if(21-total>=10){
// total+=10;
// cout<<total;
// }
// else if(total>21)
// cout<<0;
// else
// cout<<total;
// return 0;
// }
// 1.B
// 2.B
// 3.C
// 4.A
// 第1题
// int main(){
// int n;
// cin>>n;
// cout<<n*3;
// return 0;
// }
// 第2题
// int main(){
// int n,cnt=0;
// cin>>n;
// for(int i=1;i<n;i++){
// if(i*3==n){
// cout<<i-1<<i<<i+1<<endl;
// cnt+=1;
// }
// }
// if(cnt==0)
// cout<<"-1";
// return 0;
// }
// 小のman~
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// string s1;
// getline(cin,s1);
// cout<<s1<<endl;
// string s2="Hello world!";
// cout<<s2<<endl;
// string c1,c2;
// cin>>c1>>c2;
// cout<<c1<<endl<<c2<<endl<<c1.size()<<endl<<c2.size();
// return 0;
// }
// 小のman~
// int main(){
// string c1;
// getline(cin,c1);
// cout<<c1.size();
// }
// 小のman~
// int main(){
// string c1;
// getline(cin,c1);
// int l =c1.size();
// for(int i=0;i<=l-1;i++){
// if(c1[i]>='A'&& c1[i]<='Z'){
// cout<<c1[i];
// break;
// }
// }
// return 0;
// }
// 小のman~
// int main(){
// string s1,s2,s3;
// s2="Hello";
// s1=s2;
// cout<<s1;
// s3=s1+s2;
// cout<<s3;
// }
// 小のman~
// int main(){
// string c1,c2;
// getline(cin,c1);
// getline(cin,c2);
// if(c1<c2)
// cout<<c2+c1;
// if(c1>c2)
// cout<<c1+c2;
// return 0;
// }
// 小のman~
// int main(){
// string c1;
// int cnt=0;
// getline(cin,c1);
// int l =c1.size();
// for(int i=0;i<=l-1;i++){
// if(c1[i]>='0'&& c1[i]<='9'){
// cnt+=1;
// }
// }
// cout<<cnt;
// return 0;
// }
// int main(){
// char c1[123];
// cin>>c1;
// int l=strlen(c1);
// for(int i=0;i<l;i++){
// int (c1[i]);
// }
// for(int j=0;j<l-1;j++){
// cout<<char(c1[j]+c1[j+1]);
// }
// cout<<char(c1[0]+c1[l-1]);
// return 0;
// }
// 小のman~
// ???????????????????????
// 小のman~
// int main(){
// char c[213];
// int cnt;
// cin>>c;
// for(int i=0;i<strlen(c);i++){
// cnt+=int(c[i])-48;
// }
// cout<<cnt;
// string v;
// int tnt;
// cin>>v;
// for(int i=0;i<size(v);i++){
// cnt+=int(v[i])-48;
// }
// cout<<cnt;
// }
// 小のman~
// int main(){
// string mi ,c1;
// int n;
// cin>>n;
// cin>>mi;
// for(int i=2;i<=n;i++){
// cin>>c1;
// if(c1<mi){
// mi=c1;
// }
// }
// cout<<mi;
// return 0;
// }
// 小のman~
// int main(){
// string c,v;
// cin>>c>>v;
// int p=c.find(v);
// if (p==-1){
// cout<<"no";
// }
// else
// cout<<p;
// return 0;
// }
// 小のman~
// int main(){
// string c;
// cin>>c;
// int p=c.find(' ');
// cout<<p<<endl;
// int p1=s.find(' ',p+1);
// cout<<p1<<endl;
// string p2;
// p2=c.substr(p+1,p1-p);
// cout<<p2;
// return 0;
// }
// 小のman~
// int main(){
// string s;
// cin >>s;
// int t=0;
// set<string>man;
// for(int i=0;i<s.size()-2;i++){
// if(s[i]!=s[i+1]&& s[i+1]==s[i+2]){
// t+=1;
// man.insert(s.substr(i,3));
// }
// }
// cout<<t<<' ';
// cout<<man.size();
// return 0;
// }
// 小のman~
// int main(){
// int n,m;
// cin>>n>>m;
// int cnt=0;
// for(int i=n;i<=m;i++){
// int j=i;
// int tmp =0;
// while(j!=0){
// int k= j%10;
// if(k%2==0){
// tmp++;
// break;
// }
// j=j/10;
// }
// if(tmp==0)
// cnt++;
// }
// cout<<cnt;
// return 0;
// }
// 小のman~
// int main(){
// int n,m;
// cin>>n>>m;
// cout<<n*m;
// return 0;
// }
// 小のman~
// int main(){
// for (int i=1;i<=3;i++){
// int n;
// cin>>n;
// if(n%2==0)
// cout<<1<<' ';
// else
// cout<<0<<' ';
// }
// return 0;
// }
// 小のman~
// bool magic(int x){
// int y=x;
// while(y!=0){
// if((y%10)!=0&&x%(y%10)!=0){
// return false;
// }
// y /=10;
// }
// return true;
// }
// int main(){
// int n,m;
// cin>>n>>m;
// int cnt=0;
// for(int i=n;i<=m;i++){
// if(magic(i) ==true){
// cout<<i<<endl;
// cnt +=1;
// }
// }
// if(cnt==0){
// cout<<-1;
// }
// return 0;
// }
// 小のman~
// int main(){
// int n;
// cin>>n;
// cout<<(n+1)*(n+1);
// return 0;
// }
// 小のman~
// int main(){
// char n;
// cin >>n;
// switch(n){
// case 'A':
// cout<<"Apple";
// break;
// case 'B':
// cout<<"Banana";
// break;
// case 'P':
// cout<<"Pear";
// break;
// case 'O':
// cout<<"Orange";
// break;
// }
// return 0;
// }
// A A C
// B A D C C
// int main(){
// int n,a;
// cin>>n;
// int max1=0,min1=1234567;
// for(int i=1;i<=n;i++){
// int fen=0;
// for(int j=1;j<=6;j++){
// cin>>a;
// fen+=a;
// }
// if(max1<fen)
// max1 =fen;
// if(min1>fen)
// min1=fen;
// }
// cout<<max1-min1;
// int num;
// cin>>num;
// int tmp;
// tmp=num;
// while(num!=0){
// cout<<num%10<<" ";
// num=num/10;
// }
// return 0;
// }
// int main(){
// int num,cnt=0;
// cin>>num;
// int tmp;
// tmp=num;
// while(num!=0){
// cnt+=1;
// num=num/10;
// }
// cout<<cnt;
// return 0;
// }
// int main(){
// int num;
// cin>>num;
// int tmp;
// tmp=num;
// for(int i=1;i<=num;i++){
// int tmp;
// tmp=i;
// int cnt=0;
// while(i!=0){
// cnt+=i%10;
// i=i/10;
// }
// if(cnt%2==0)
// cout<<tmp<<" ";
// }
// return 0;
// }
// int main(){
// string s;
// cin>>s;
// for(int i=0;i<s.size();i++){
// if(i%2==0)
// cout<<s[i];
// else if(s[i]=='W')
// cout<<'M';
// else cout'W';
// }
// return 0;
// }
// int main(){
// string s;
// cin>>s;
// int cnt;
// cout<<s.size();
// for(int i=0;i<s.size();i++){
// if(s[i]=='.')
// cnt++;
// }
// cout<<cnt;
// return 0;
// }
// int main(){
// string s;
// int n;
// cin>>s>>n;
// for(int i=0;i<s.size();i++){
// if(s[i]>='A'&&s[i]<='Z'){
// if(s[i]+n<='Z'){
// s[i]+=n;
// }else{
// s[i]=s[i]+n-'Z'+'A'-1;
// }
// }else if(s[i]>='a'&&s[i]<='z'){
// if(s[i]+n<='z'){
// s[i]+=n;
// }else{
// s[i]=s[i]+n-'z'+'a'-1;
// }
// }
// }
// cout<<s;
// return 0;
// }
// 回文判断
// int main(){
// string s;
// cin>>s;
// string s1=s;
// int l=s1.size();
// for(int i=0;i<l;i++){
// s1[l-1-i]=s[i];
// }
// if(s==s1){
// cout<<'y';
// }
// else{
// cout<<'n';
// }
// cout<<s1;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n[105],a;
// cin>>a;
// for (int i=0;i<=a-1;i++){
// cin>>n[i];
// }
// for (int i=0;i<=a-2;i++){
// if(n[i-1]<n[i]&&n[i+1]<n[i])
// cout<<n[i]<<endl;
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,a[16],s=0;
// cin>>n;
// for (int i=0;i<=n-1;i++){
// cin>>a[i];
// s+=a[i];
// }
// double v=s*1.0/n;
// cout<<"AVE=";
// printf("%.1f",v);
// cout<<endl;
// for(int d=0;d<n;d++){
// if(a[d]>v)
// cout<<d+1<<":"<<a[d]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,a[201];
// cin>>n;
// for(int i=0;i<n;i++){
// cin>>a[i];
// if(a[i]*a[i]%7!=1)
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,cnt=0;
// int a[105];
// cin>>n;
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// int m,k;
// m =a[i];
// int cnt=0;
// while(m!=0){
// k=m%10;
// if(k%2!=0){
// cnt=1;
// break;
// }
// cnt += 1;
// m/=10;
// }
// if(cnt % 2 == 0){
// cout<<a[i]<<endl;
// }
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,m,cnt=0;
// int a[101];
// cin>>n;
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// cin>>m;
// for(int i=0;i<n;i++){
// if(a[i]==m){
// cout<<i+1;
// cnt+=1;
// break;
// }
// }
// if(cnt==0)
// cout<<"-1";
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,a[21],MAX=0,MIN=32768;
// cin>>n;
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(a[i]>MAX){
// MAX=a[i];
// }
// }
// cout<<MAX<<" ";
// for(int i=0;i<n;i++){
// if(a[i]<MIN){
// MIN=a[i];
// }
// }
// cout<<MIN;
// return 0;
// }
// printf("%.2f",mhgchgcs jg)
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// int a[101];
// cin>>n;
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=n-1;i>=0;i--){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// int a[101];
// cin>>n;
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n/2;i++){
// swap(a[i],a[n-i-1]);
// }
// for(int i=0;i<n;i++)
// cout<<a[i]<<" ";
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// double s=0;
// cin>>n;
// int a[11],MAX=0,MIN=32768;
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(a[i]>MAX){
// MAX=a[i];
// }
// }
// for(int i=0;i<n;i++){
// if(a[i]<MIN){
// MIN=a[i];
// }
// }
// for(int i=0;i<n;i++){
// s+=a[i];
// }
// printf("%.2f",(s-MAX-MIN)/(n-2));
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[15];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// int x;
// cin>>x;
// x--;
// for(int i=x;i<=n-2;i++){
// a[i]=a[i+1];
// }
// n--;
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,min=21472147,x;
// cin>>n;
// int a[105];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(min>a[i]){
// min=a[i];
// x=i;
// }
// }
// for(int i=x;i<=n-2;i++){
// a[i]=a[i+1];
// }
// n--;
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[105];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// int x,y;
// cin>>x>>y;
// x--;
// for(int i=n-1;i>=x;i--){
// a[i+1]=a[i];
// }
// a[x]=y;
// n++;
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int m,n,z;
// cin>>m>>n;
// int a[105];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(a[i]>m){
// z=i;
// break;
// }
// }
// for(int j=n-1;j>=z;j--){
// a[j+1]=a[j];
// }
// a[z]=m;
// n++;
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int m,n,z,max=0;
// cin>>n;
// int a[105];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// cin>>m;
// for(int i=0;i<n;i++){
// if(max<a[i]){
// max=a[i];
// z=i;
// }
// }
// for(int j=n-1;j>=z;j--){
// a[j+1]=a[j];
// }
// a[z+1]=m;
// n++;
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,min=96584,x,t;
// cin>>n;
// int a[205];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(a[i]<min){
// min=a[i];
// x=i;
// t=i;
// }
// }
// cout<<x+1<<endl;
// swap(a[0],a[t]);
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,x,y,z;
// cin>>n>>x>>y;
// int a[205];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(a[i]==x){
// for(int j=n-1;j>i;j--)
// a[j+1]=a[j];
// z=i;
// break;
// }
// }
// n++;
// a[z+1]=y;
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,min=96584,max=0,x,t;
// cin>>n;
// int a[205];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(a[i]<min){
// min=a[i];
// t=i;
// }
// }
// for(int i=0;i<n;i++){
// if(a[i]>max){
// max=a[i];
// x=i;
// }
// }
// swap(a[x],a[t]);
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[15];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=1;i<n;i++){
// for(int j=0;j<=n-2;j++){
// if(a[j]>a[j+1]){
// swap(a[j],a[j+1]);
// }
// }
// }
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,min=96584,max=0,x,t;
// cin>>n;
// int a[205];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=0;i<n;i++){
// if(a[i]<min){
// min=a[i];
// t=i;
// }
// }
// for(int i=0;i<n;i++){
// if(a[i]>max){
// max=a[i];
// x=i;
// }
// }
// swap(a[t],a[0]);
// swap(a[x],a[n-1]);
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[15];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// int cnt=0;
// for(int i=0;i<n;i++){
// cnt+=a[i];
// }
// cout<<cnt<<endl;
// double n1=n;
// printf("%.2f",cnt/n1);
// cout<<endl;
// for(int i=1;i<n;i++){
// for(int j=0;j<=n-2;j++){
// if(a[j+1]>a[j]){
// swap(a[j],a[j+1]);
// }
// }
// }
// for(int i=0;i<n;i++){
// cout<<a[i]<<" ";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[105];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=1;i<=n-1;i++){
// for(int j=0;j<=n-1-i;j++){
// if(a[j+1]<a[j]){
// swap(a[j+1],a[j]);
// }
// }
// }
// if(n%2==0){
// printf("%.1f",(a[n/2]+a[n/2-1])/2.0);
// }
// else{
// printf("%.1f",a[n/2]/1.0);
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,k;
// cin>>n>>k;
// int a[105];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=1;i<=n-1;i++){
// for(int j=0;j<=n-1-i;j++){
// if(a[j+1]>a[j]){
// swap(a[j+1],a[j]);
// }
// }
// }
// cout<<a[k-1];
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,k,cnt=0,tnt=0;
// cin>>n>>k;
// int a[105];
// for(int i=0;i<k;i++){
// cin>>a[i];
// }
// for(int i=1;i<=k-1;i++){
// for(int j=0;j<=k-1-i;j++){
// if(a[j+1]>a[j]){
// swap(a[j+1],a[j]);
// }
// }
// }
// for(int i=0;i<k;i++){
// if(cnt<n){
// cnt+=a[i];
// tnt+=1;
// }
// else if(cnt>=n){
// break;
// }
// }
// if(cnt<n)
// {
// cout<<"NO";
// }
// else{
// cout<<tnt;
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// int x,t;
// cin>>n;
// int a[10]={0};
// for(int i=1;i<=n;i++){
// x=i;
// while(x!=0){
// t=x%10;
// a[t]=a[t]+1;
// x=x/10;
// }
// }
// for(int i=0;i<10;i++){
// cout<<a[i]<<endl;
// }
// return 0;
// }
// 随机数模板
// 1
// int max = 最大范围 ;
// int min = 最小范围 ;
// int c =min+rand()%(max-min+1);
// cout<<c<<endl;
// 2
// int d=rand();
// cout<< 最小范围 +d%(最大范围-最小范围+1)<<endl;
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// int x,t=0;
// cin>>n;
// int a[101];
// for(int i=0;i<n;i++){
// cin>>a[i];
// }
// for(int i=1;i<=n-1;i++){
// for(int j=0;j<=n-1-i;j++){
// if(a[j+1]>a[j]){
// swap(a[j+1],a[j]);
// }
// }
// }
// for(int i=0;i<=4;i++){
// t+=a[i];
// }
// printf("%.1f",t/5.0);
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int x,t;
// int a[50];
// int c[25]={0};
// for(int i=0;i<50;i++){
// cin>>a[i];
// c[a[i]]=c[a[i]]+1;
// }
// int max=0;
// for(int i=0;i<20;i++){
// if(c[i]>max){
// max=c[i];
// }
// }
// cout<<max;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// int a[105];
// int t[1005]={0};
// int x;
// cin>>n;
// int k=0;
// for(int i=0;i<n;i++){
// cin>>x;//一個小銀子
// if(t[x]==0){
// t[x]=1;
// a[k]=x;
// k++;
// }
// }
// for(int i=1;i<=k-1;i++){
// for(int j=0;j<=k-1-i;j++){
// if(a[j]>a[j+1]){
// swap(a[j],a[j+1]);
// }
// }
// }
// cout<<k<<endl;
// for(int i=0;i<k;i++)cout<<a[i]<<endl;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,z=0;
// cin>>n;
// int a[10001];
// int q[105]={0};
// for(int i=0;i<n;i++){
// cin>>a[i];
// z+=a[i];
// q[a[i]]++;
// }
// printf("%.2f",z/1.0/n);
// cout<<" ";
// int asd=0,qwer=0;
// for(int i=0;i<105;i++)
// {
// if(q[i]>asd){
// asd=q[i];
// qwer=i;
// }
// }
// cout<<qwer<<" ";
// for(int i=1;i<=n-1;i++){
// for(int j=0;j<=n-1-i;j++){
// if(a[j]>a[j+1]){
// swap(a[j],a[j+1]);
// }
// }
// }
// if(n%2==0){
// printf("%.1f",(a[n/2]+a[n/2-1])/2.0);
// }
// else if(n%2!=0){
// printf("%.1f",a[n/2]/1.0);
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,m,k=0,a[1005]={0};
// cin>>n>>m;
// for(int i=0;i<=n;i++){
// for(int j=0;j<=m;j++){
// a[k]=i*3+j*5;
// k++;
// }
// }
// for(int i=1;i<=k-1;i++){
// for(int j=0;j<=k-1-i;j++){
// if(a[j]>a[j+1]){
// swap(a[j],a[j+1]);
// }
// }
// }
// for(int i=1;i<k;i++){
// cout<<a[i]<<" ";
// }
// cout<<endl<<k-1;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// double k=sqrt(n);
// if(k==int (k/1)){
// cout<<"Y";
// }
// else{
// cout<<"N";
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,cnt=0;
// cin>>n;
// for(int i=2;i<=sqrt(n);i++){
// if(n%i==0){
// cnt+=1;
// break;
// }
// }
// if(cnt==0){
// cout<<"yes";
// }
// else if(cnt>0||n==1){
// cout<<"no";
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,cnt=0;
// cin>>n;
// for(int i=2;i<=sqrt(n);i++){
// if(n%i==0){
// cnt+=i;
// if(i!=n/i)
// cnt+=n/i;
// }
// }
// cout<<cnt;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// for(int i=1000;i<=9999;i++){
// int k1,k2,k3,k4;
// k1=i/1000;
// k2=i/100%10;
// k3=i/10%10;
// k4=i%10;
// double k=sqrt(i);
// if(k1==k2 && k3==k4 && k==int(sqrt(i))){
// cout<<i<<endl;
// }
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// void rap(int n){
// if(n==1){
// cout<<"全民制作人们大家好，我是练习时长两年半的实习生蔡徐坤。";
// }
// if(n==2){
// cout<<"mmmmmmmmmaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn";
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,cnt=0;
// cin>>n;
// for(int i=2;i<=sqrt(n);i++){
// if(n%i==0){
// cnt+=1;
// break;
// }
// }
// if(cnt==0&&n!=1){
// cout<<"yes";
// }
// else if(cnt>0||n==1){
// cout<<"no";
// }
// return 0;
// }
// int lasingan(int n,int m,int x){
// if(n>m>x||n>x>m){
// return n;
// }
// else if(m>n>x||m>x>n){
// return m;
// }
// else{
// return x;
// }
// }
// int main(){
// int t;
// t=lasingan(2,10,12);
// cout<<t+3;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// bool sushu(int n){
// bool r=true;
// for(int i=2;i<=sqrt(n);i++){
// if(n % i==0){
// r=false;
// break;
// }
// }
// if(n<=1){
// r=false;
// }
// return r;
// }
// int main(){
// for(int i=1000;i<=2999;i++){
// int a,b,c;
// a=i%1000;
// b=i%100;
// c=i%10;
// if(sushu(i)==true&& sushu(a) ==true&& sushu(b)==true&&sushu(c)==true)
// {
// cout<<i<<endl;
// }
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// bool sushu(int n){
// bool r=true;
// for(int i=2;i<=sqrt(n);i++){
// if (n%i==0){
// r=false;
// }
// }
// if(n<=1){
// r=false;
// }
// return r;
// }
// int main(){
// int q;
// cin>>q;
// for(int i=2;i<=q-2;i++){
// if(sushu(i)==true&&sushu(i+2)==true){
// cout<<i<<" "<<i+2<<endl;
// }
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// bool sushu(int n){
// bool r=false;
// for(int i=2;i<=sqrt(n);i++){
// if (n%i==0){
// r=true;//合数
// }
// }
// if(n<=1){
// r=false;
// }
// return r;
// }
// int main(){
// for(int i=100;i<=999;i++){
// int a,b;
// a=i/100;
// b=i/10;
// if(sushu(i)==true&& sushu(a) ==true&& sushu(b)==true)
// {
// cout<<i<<endl;
// }
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int yinzihe(int n){
// int s=0;
// for(int i=2;i<=n-1;i++){
// if(n%i==0){
// s+=i;
// }
// }
// return s;
// }
// int main(){
// int k;
// cin>>k;
// for(int i=2;i<=k;i++){
// for(int j=2;j<=k;j++){
// if(yinzihe(i)==j&&yinzihe(j)==i){
// cout<<i<<" "<<j<<endl;
// }
// }
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int huiwen(int n){
// int t=0;
// while(n!=0)
// {
// t=t*10+n%10;
// n=n/10;
// }
// return t;
// }
// int main()
// {
// int n;
// int s=0;
// cin>>n;
// for(int i=1;i<=n;i++)
// {
// if(huiwen(i)==i){
// s+=1;
// }
// }
// cout<<s;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int huiwen(int n){
// int t=0;
// while(n!=0)
// {
// t=t*10+n%10;
// n=n/10;
// }
// return t;
// }
// bool sushu(int n){
// bool r=true;
// for(int i=2;i<=sqrt(n);i++){
// if (n%i==0){
// r=false;
// }
// }
// if(n<=1){
// r=false;
// }
// return r;
// }
// int main()
// {
// for(int i=10;i<=1000;i++)
// {
// if(sushu(i)==true&&huiwen(i)==i)
// {
// cout<<i<<endl;
// }
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int yinzihe(int n){
// int s=0;
// for(int i=1;i<=n-1;i++){
// if(n%i==0){
// s+=i;
// }
// }
// return s;
// }
// int main(){
// int v,cnt=0;
// cin>>v;
// for(int i=1;i<=v;i++){
// if(i==yinzihe(i)){
// cnt++;
// }
// }
// cout<<cnt;
// return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n){
// int r;
// if(n==1){
// r=1;
// }
// else{
// r=num(n-1)*2;
// }
// return r;
// }
// int main(){
// cout<<num(6);
// return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n){
// int r;
// if(n==1){
// r=1;
// }
// else{
// r=num(n-1)*n;
// }
// return r;
// }
// int main(){
// cout<<num(6);
// return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n){
// int r;
// if(n==1||n==2){
// r=1;
// }
// else{
// r=num(n-1)+num(n-2);
// }
// return r;
// }
// int main(){
// int v;
// cin>>v;
// cout<<num(v);
// return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n){
// int r;
// if(n==1){
// r=1;
// }
// else{
// r=num(n-1)+n-1;
// }
// return r;
// }
// int main(){
// int cnt,i=1;
// while(cnt<5000){
// cnt+=num(i);
// i++;
// }
// cout<<cnt;
// return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n){
// int r;
// if(n==1||n==2){
// r=1;
// }
// else{
// r=num(n-1)+num(n-2);
// }
// return r;
// }
// int main(){
// int v;
// double cnt=0;
// for(int i=1;i<=v;i++){
// cnt+=num(i)*1.0/num(i+1);
// }
// printf("%.3f",cnt);
// return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n){
// int r,i=1,cnt=0;
// if(n==1){
// r=1;
// }
// else{
// r=num(n-1)+n;
// n--;
// }
// return r;
// }
// int main(){
// int v,cnt=0;
// cin>>v;
// for(int i=1;i<=v;i++){
// cnt+=num(i);
// }
// cout<<cnt;
// return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n){
// int r,i=1,cnt=0;
// if(n==1){
// r=1;
// }
// else{
// r=num(n-1)+n-1;
// n--;
// }
// return r;
// }
// int main(){
// int v,cnt=0;
// cin>>v;
// for(int i=1;i<=v;i++){
// cnt+=num(i);
// }
// cout<<cnt;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int b[3][4];
// for(int i=0;i<=2;i++){
// for(int j=0;j<=3;j++){
// b[i][j]=0;
// }
// }
// b[1][1]=99;
// b[2][2]=87;
// b[0][3]=72;
// b[0][1]=100;
// b[0][2]=98;
// b[2][1]=92;
// b[2][3]=93;
// b[1][2]=98;
// b[1][3]=97;
// for(int i=0;i<=2;i++){
// for(int j=0;j<=3;j++){
// cout<<b[i][j]<<" ";
// }
// cout<<endl;
// }
// int c[2][2]={
// {9,7},
// {2,8},
// };
// for(int i=0;i<=1;i++){
// for(int j=0;j<=1;j++){
// cout<<c[i][j]<<" ";
// }
// cout<<endl;
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,v;
// cin>>n>>v;
// int c[15][15];
// for(int i=1;i<=n;i++){
// for(int j=1;j<=v;j++){
// cin>>c[i][j];
// }
// }
// int max=c[1][1],min=c[1][1];
// for(int i=1;i<=n;i++){
// for(int j=1;j<=v;j++){
// if (max < c[i][j]){
// max=c[i][j];
// }
// if (min > c[i][j]){
// min=c[i][j];
// }
// }
// }
// cout<<max-min;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int c[105][3];
// for(int i=1;i<=n;i++){
// for(int j=1;j<=3;j++){
// cin>>c[i][j];
// }
// }
// int s1=0,s2=0,s3=0;
// for(int i=1;i<=n;i++){
// s1+=c[i][1];
// }
// for(int i=1;i<=n;i++){
// s2+=c[i][2];
// }
// for(int i=1;i<=n;i++){
// s3+=c[i][3];
// }
// printf("%.1f",(s1/1.0/n));
// cout<<" ";
// printf("%.1f",(s2/1.0/n));
// cout<<" ";
// printf("%.1f",(s3/1.0/n));
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[15][15]={0};
// for(int i=0;i<n;i++){
// for(int j=0;j<=i;j++){
// if(j==0){
// a[i][j]=1;
// }
// else{
// a[i][j]=a[i-1][j]+a[i-1][j-1];
// }
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<=i;j++){
// cout<<a[i][j]<<" ";
// }
// cout<<endl;
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int a=0,b=0;
// int c[105][105]={0};
// int n,m;
// cin>>n>>m;
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// cin>>c[i][j];
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// if(c[i][j]%2==0){
// a++;
// }
// else{
// b++;
// }
// }
// }
// cout<<b<<" "<<a;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int c[105][3]={0};
// int n;
// double m,max=0;
// cin>>n;
// for(int i=0;i<n;i++){
// for(int j=0;j<3;j++){
// cin>>c[i][j];
// }
// }
// for(int i=0;i<n;i++){
// m=(c[i][1]+c[i][0])*c[i][2]/2.0;
// if(m>max){
// max=m;
// }
// }
// printf("%.1f",max);
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,m;
// cin>>n>>m;
// int cnt=0;
// double a=0;
// int c[105][105]={0};
// int b[105][105]={0};
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// cin>>c[i][j];
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// cin>>b[i][j];
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<m;j++){
// if(c[i][j]==b[i][j]){
// cnt++;
// }
// }
// }
// a=cnt/1.0/(n*m);
// printf("%.2f",a*100);
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int a[15][15]={0};
// int n;
// cin>>n;
// int cnt=n*n;
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// a[i][j]=cnt;
// cnt++;
// }
// }
// for(int i=n-1;i<0;i++){
// for(int j=0;j<n;j++){
// cout<<setw(3)<<a[i][j];
// }
// cout<<endl;
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int cnt=1;
// int a[105][105]={0};
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// a[j][n-1-i]=cnt;
// cnt++;
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<setw(3)<<a[i][j];
// }
// cout<<endl;
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,x=0;
// cin>>n;
// int a[15][15]={0};
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<n;j++){
// a[i-j][j]=i+1;
// a[n-1-j][j+(n-1-i)]=(2*n-1)-i;
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<setw(3)<<a[i][j];
// }
// cout<<endl;
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,x=0;
// cin>>n;
// int a[15][15]={0};
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<n;j++){
// a[i][j+i]=i+1;
// a[j+i][i]=i+1;
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<setw(3)<<a[i][j];
// }
// cout<<endl;
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int cnt=1;
// int a[105][105]={0};
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// a[4-i][4-j]=cnt;
// cnt++;
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<setw(3)<<a[i][j];
// }
// cout<<endl;
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,cnt=1;
// cin>>n;
// int a[105][105]={0};
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<n;j++)
// {
// a[n-1-j-i][n-1-i]=i+1;
// a[n-1-i][n-1-j-i]=i+1;
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cout<<setw(3)<<a[i][j];
// }
// cout<<endl;
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[105][105]={0};
// int k=1;
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(i==0){
// a[j][j]=k;
// k++;
// }
// else {
// a[j][j+i]=a[j][j+i-1]+a[j+1][j+i];
// }
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(a[i][j]==0){
// cout<<setw(5)<<" ";
// }
// else if(a[i][j]!=0)
// cout<<setw(5)<<a[i][j];
// }
// cout<<endl;
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[105][105]={0};
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(i==0){
// a[j][j]=i+1;
// }
// else {
// a[j][j+i]=i+1;
// }
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(a[i][j]==0){
// cout<<setw(5)<<" ";
// }
// else if(a[i][j]!=0)
// cout<<setw(5)<<a[i][j];
// }
// cout<<endl;
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[105][105]={0};
// for(int i=0;i<n;i++){
// for(int j=0;j<n- i;j++){
// if(i==0){
// a[n-1-j][i+j]=i+1;
// }
// else {
// a[i+j][n-1-j]=i+1;
// }
// }
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(a[i][j]==0){
// cout<<setw(5)<<" ";
// }
// else if(a[i][j]!=0)
// cout<<setw(5)<<a[i][j];
// }
// cout<<endl;
// }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main (){
// int a[105][6]={0};
// int n;
// int num[100]={0};
// int sum=0;
// double s[100]={0};
// int mx,mi;
// cin>>n;
// for(int i=0;i<n;i++){
// for(int j=0;j<6;j++){
// cin>>a[i][j];
// }
// mx=a[i][1];
// mi=a[i][1];
// sum=0;
// for(int k=1;k<6;k++){
// sum=sum+a[i][k];
// if(a[i][k]>mx){
// mx=a[i][k];
// }
// if(a[i][k]<mi){
// mi=a[i][k];
// }
// }
// s[i]=(sum-mx-mi)*1.0/3;
// num[i]=a[i][0];
// // printf("%.3f",s[i]);
// // cout<<endl;
// }
// for(int i=1;i<n;i++){
// for(int j=0;j<=n-1-i;j++){
// if(s[j]<s[j+1]){
// swap(s[j],s[j+1]);
// swap(num[j],num[j+1]);
// }
// }
// }
// for(int i=0;i<3;i++){
// cout<<num[i]<<" ";
// printf("%.3f",s[i]);
// cout<<endl;
// }
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n;
// cin>>n;
// int a[15][15]={0};
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// cin>>a[i][j];
// }
// }
// int cnt=0;
// for(int i=0;i<n;i++){
// cnt+=a[i][i];
// }
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// if(i+j==n-1){
// cnt+=a[i][j];
// }
// }
// }
// cout<<cnt;
// return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main(){
// int n,m,k,cnt=0;
// cin>>n>>m>>k;
// int a[1005][10]={0};
// for(int i=0;i<n;i++){
// for(int j =0;j<m;j++){
// cin>>a[i][j];
// }
// }
// for(int i=0;i<n;i++){
// int s=0;
// for(int j=0;j<m;j++){
// s+=a[i][j];
// }
// if(s>=k){
// cnt++;
// }
// }
// cout<<cnt;
// return 0;
// }
#include<bits/stdc++.h>
using namespace std;
int main(){
int x,y;
int n;
cin>>x>>y;
cin>>n;
int k=20005;
int ind,men;
int a[105][2]={0};
for(int i=0;i<n;i++){
cin>>a[i][0]>>a[i][1];
}
for(int i=0;i<n;i++){
if(x!=a[i][0]||y!=a[i][1]){
int juli =abs(a[i][0]-x)+abs(a[i][1]-y);
// cout<<juli<<endl;
if(juli<k){
k=juli;
ind=i;
men=abs(a[i][0])+abs(a[i][1]);
}
else if(k==juli){
if(men>a[i][0]+a[i][1]);
}
}
}
cout<<a[ind][0]<<" "<<a[ind][1];
return 0;
}
/**************************************************************
Problem: 1347
User: luyanchen
Language: C
Result: Compile Error
****************************************************************/