Cod sursa(job #1691070)

Utilizator PaulMarinaFitPaul Marina Fit PaulMarinaFit Data 16 aprilie 2016 19:34:51
Problema Elementul majoritar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 38.04 kb
//connect 188.212.105.171:27015
//
#include <iostream>
#include <fstream>
using namespace std;
int v[1000001],n;
ifstream f("elmaj.in");ofstream g("elmaj.out");
int main()
{
   int nr=0, c,m;
   f>>n;
   for (int i = 1; i <= n; i++)
   {
       f>>v[i];
       if(nr==0)
       {
           c=v[i];
           nr=1;
       }
       else
          if(v[i]==c) nr++;
          else nr--;
   }
    m = 0;
    for (int i = 1; i <= n; i++)
       if (v[i] == c) m++;

    if (m > n / 2)
        g<<c<<" "<<m;
    else
        g<<-1;

    f.close();g.close();
    return 0;
}

//#include <fstream>
//
//using namespace std;
//char fr[1000001];
//int mini=1000000,maxi,maxx,c,mm,i,a,n,nr,m,j;
//int main()
//{ifstream f("proiecte.in");
//ofstream g("proiecte.out");
//int p[200001];
//f>>n>>m;
//for(j=1;j<=m;j++)
//{f>>a; nr=0;
// for (int i = 1; i <= a; i++)
//   {
//       f>>p[i];
//       if(nr==0)
//       {
//           c=p[i];
//           nr=1;
//       }
//       else
//          if(p[i]==c) nr++;
//          else nr--;
//   }
//    mm= 0;
//    for (int i = 1; i <= a; i++)
//       if (p[i] == c) mm++;
//       if(mm>a/2)
//        {
//            fr[c]++;
//            maxx=max(maxx,(int)fr[c]);
//           if(c<mini)     mini=c;
//           if(c>maxi)     maxi=c;
//        }
//
//}
// for(i=mini;i<=maxi;i++)
//  if(fr[i]==maxx) g<<i<<" ";
//
//    return 0;
//}
//#include <iostream>
//#include <cmath>
//#include <algorithm>
//#include <fstream>
//using namespace std;
//ifstream f("uscat.in");
//ofstream g("uscat.out");
//int r,b,k,cif,j,p,s1,s2,s3,i,m,x,nn,z,l;
//long long a[100001],s,maxi,c,n,mini ;
//
//int main()
//{
// f>>n>>a[1];maxi=a[1];
// for(i=2;i<=n;i++)
// {
//     f>>a[i];
//     if(a[i]>maxi)maxi=a[i];
// }
// f>>c;z=maxi/2;
//if(maxi%2==1)z++;
//for(i=1;i<=n;i++)
//if(a[i]<=z)a[i]=0;
//
//for(i=1;i<=n;i++)
//{
//    if(a[i]>0)
//    {if(maxi==a[i]){a[i]=a[i]-c;}
//    else a[i]--;
//    }
//    if(a[i]>maxi-c)maxi=a[i],k++;
//
//}
//g<<k;
//return 0;
//
//}
//
//#include <fstream>
//using namespace std;
//ifstream fi("mesaj3.in");
//ofstream fo("mesaj3.out");
//int t,lim,lun,k,L,j,i,n,m,ord[100],fr[300];
//char c[100],cuv[100],ss[2001],s[2001],a[2001][30];
//int main()
//{
//   fi>>n; fi>>cuv;
//   fi>>m;fi.get();
//   for(i=0;i<m;i++)s[i]=fi.get();
//for(i=0;i<m;i++)fr[s[i]]++;
//int mini=2000000;char sol;
//for(i=1;i<=200;i++)
//  if(fr[i]!=0 and fr[i]<mini){mini=fr[i];sol=i;}
//  fo<<(char)sol<<endl;;
//   for(i=0;i<n;i++)c[i+1]=cuv[i];
//   for(i=1;i<=n;i++)ord[i]=i;
//   for(i=1;i<=n;i++)
//     for(j=i+1;j<=n;j++)
//   if(c[i]>c[j]){swap(c[i],c[j]);swap(ord[i],ord[j]);}
//   lun=m/n;
//   lim=m%n;
//   for(t=1;t<=n;t++)
//      {
//          if(ord[t]<=lim)L=lun+1;
//          else L=lun;
//          for(i=1;i<=L;i++)a[i][ord[t]]=s[k++];
//      }
//    if(lim!=0)lun++;
//    k=0;
//    for(i=1;i<=lun;i++)
//        for(j=1;j<=n;j++)ss[k++]=a[i][j];
//    ss[m]=0;
//   fo<<ss;
//   fo<<endl;
//   return 0;
//}

//#include <fstream>
//using namespace std;
//ifstream fi("axyz.in");
//ofstream fo("axyz.out");
//int a[30003],b[30003],c[30003],d[30003];
//int c3,c1,c2,jj,A,v,maxi,i,j,n,m,p,q,lin,col;
//int main()
//{
//   fi>>v>>A>>n;
//   for(i=1;i<=n;i++)fi>>a[i];
//if(v==1){
//       i=n;
//       while(a[i]>=a[i-1] and i>=2)i--;
//       i--;
//       for(j=i;j<=n;j++)
//        if(a[i]>a[j])p=j;
//       swap(a[i],a[p]);
//       j=i+1;jj=n;
//       while(j<jj){swap(a[j],a[jj]);j++;jj--;}
//       for(i=1;i<=n;i++)fo<<a[i];
//}
//if(v==2){
//    if(A<100){
//            c1=A/10;c2=A%10;
//            for(i=n;i>=1;i--)
//                if(a[i]==c2)b[i]=b[i+1]+1;
//                else b[i]=b[i+1];
//            for(i=n;i>=1;i--)
//                if(a[i]==c1)c[i]=c[i+1]+b[i];
//                else c[i]=c[i+1];
//
//    fo<<c[1];
//    }
//    if(A>=100){
//            c1=A/100;c2=A/10%10;c3=A%10;
//            for(i=n;i>=1;i--)
//                if(a[i]==c3)b[i]=b[i+1]+1;
//                else b[i]=b[i+1];
//            for(i=n;i>=1;i--)
//                if(a[i]==c2)c[i]=c[i+1]+b[i];
//                else c[i]=c[i+1];
//            for(i=n;i>=1;i--)
//                if(a[i]==c1)d[i]=d[i+1]+c[i];
//                else d[i]=d[i+1];
//    fo<<d[1];
//    }
//}
//     return 0;
//}

//cout<<"Formeaza triunghi isoscel";cout<<"Nu formeaza triunghi isoscel";
//#include <iostream>
//#include <cmath>
//#include <algorithm>
//#include <fstream>
//using namespace std;
//ifstream f("muzical.in");
//ofstream g("muzical.out");
//int k,cif,j,maxi,s1,s2,s3,i,m,x,mini;
//long long s,a,n,p ;
//char muzica;
//int main()
//{
//    f>>n;
//    for(i=1;i<=n;i++)
//    { f>>muzica;
//    if(muzica=="do1")s=s+0;
//    if(muzica=="re")s=s+1;
//    if(muzica=="mi")s=s+2;
//    if(muzica=="fa")s=s+3;
//    if(muzica=="sol")s=s+4;
//    if(muzica=="la")s=s+5;
//    if(muzica=="si")s=s+6;
//    if(muzica=="do2")s=s+7;
//
//    }
//    m=s%8;
//    if(m==0)g<<"do1";
//    if(m==7)g<<"do2";
//    if(m==1)g<<"re";
//    if(m==2)g<<"mi";
//    if(m==3)g<<"fa";
//    if(m==4)g<<"sol";
//    if(m==5)g<<"la";
//    if(m==6)g<<"si";
//
//return 0;
//}
//#include <fstream>
//
//using namespace std;
//int n,i,m,a[101][101],b[101][101],j,l,ll,z,r,v;
//int main()
//{ifstream f("copaci1.in");
//ofstream g("copaci1.out");
//f>>n>>m;
//for(i=1;i<=n;i++)
//for(j=1;j<=m;j++)
//{
//    f>>a[i][j];
//    if(a[i][j]==0) r++;
//}
//while(1)
//{z++;ll=0;
//for(i=1;i<=n;i++)
//for(j=1;j<=m;j++)
//{v=0;
//if(a[i][j]==0)
//{if(a[i-1][j]==1 ) v++;
//  if(a[i][j+1]==1) v++;
//  if(a[i][j-1]==1) v++;
//  if(a[i+1][j]==1) v++;
//  if(v>=2) {b[i][j]=1;l++;ll++;}
//
//}}
//if(l==r) {g<<z;break;}
//if(ll==0) {g<<z-1<<'\n';g<<"IMPOSIBIL";break;}
//for(i=1;i<=n;i++)
//    for(j=1;j<=m;j++){
//                      if(b[i][j]==1)a[i][j]=1;
//                      b[i][j]=0;
//    }
//}
//    return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
////ifstream f("lipsa.in");
////ofstream g("lipsa.out");
//int n,i,k,a,s;
//int main()
//{
//cin>>p;
//for(i=p;i<=p;i++)
//
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream f("piramide.in");
//ofstream g("piramide.out");
//int kk,i,n,s,k,x,a[100000],piramida[100000];
//int main()
//{
//    f>>n>>x>>kk;
//    for(i=1;i<=kk;i++)f>>a[i];
//    piramida[1]=3;k=3;
//    for(i=2;i<=100;i++){
//        piramida[i]=piramida[i-1]+k; k++;
//    }
//    for(i=1;i<=100;i++)
//          if (s<x) s=s+piramida[i];
//          else  break;
//    g<<i-1<<'\n';
//    int su=0,nrp=0;
//    for(i=1;i<=500;i++){
//        nrp++;
//          if (su<=n) su=su+piramida[i];
//          else  break;
//    }
//    g<<nrp-2<<'\n'<<n-(su-piramida[i-1]);
//    return 0;
//}
//#include <fstream>
//#define M 103
//using namespace std;
//ifstream fi("joc13.in");
//ofstream fo("joc13.out");
//int castiga,poz1,poz2,s1,s2,i,j,m,n,k,p,a[M],z[M];
//int next(int i,int pas){
// int p=i+pas;
// if(p<=n)return p;
// else return p-n;
//}
//int main(){
//fi>>n;
//for(i=1;i<=n;i++)fi>>a[i];
//fi>>m;
//for(j=1;j<=m;j++)fi>>z[j];
//poz1=poz2=1;s1=s2=0;
//for(j=1;j<=m;j++){
//    if(j%2==1)
//        {
//           poz1=next(poz1,z[j]);
//           if(s1!=0 and poz1==1 and j>2){s1+=a[1];castiga=1;break;}
//           if(a[poz1]==0 or poz1==poz2){poz1=1;s1=0;}
//           else if(a[poz1]==10)s1+=10;
//                else if(a[poz1]==1)s1+=1;
//
//        }
//      if(j%2==0)
//        {
//           poz2=next(poz2,z[j]);
//           if(s2!=0 and poz2==1 and j>2){s2+=a[1];castiga=2;break;}
//           if(a[poz2]==0 or poz1==poz2){poz2=1;s2=0;}
//           else if(a[poz2]==10)s2+=10;
//                else if(a[poz2]==1)s2+=1;;
//        }
//
//}
//if(castiga==0)
//     if(s1>s2 or (s1==s2 and poz1>poz2))castiga=1;
//     else castiga=2;
//if(castiga==1){fo<<castiga<<'\n'<<poz1<<" "<<s1<<'\n'<<poz2<<" "<<s2;}
//if(castiga==2){fo<<castiga<<'\n'<<poz1<<" "<<s1<<'\n'<<poz2<<" "<<s2;}
//return 0;
//}
//#include <fstream>
//
//using namespace std;
//
//ifstream f("schi1.in");
//ofstream g("schi1.out");
//int n, a[3][100001], k, x, i, li, ls, ga,m,kk;
//int main()
//{
//  freopen("schi1.in", "r" ,stdin);
//  freopen("schi1.out", "w" ,stdout);
//  scanf("%d", &n); k = 0;
//  for(i = 1; i <= n; i++)
//  {
//    scanf("%d", &x);
//    if(x > a[1][k])
//    { k++;
//      a[1][k] = x;
//      a[2][k] = 1;
//    }
//    else
//    { if(k == 0)k++;
//    a[2][k]++;
//    }
//  }
//  m=k;
// scanf("%d", &kk);
//  for(i=1;i<=kk;i++) {
//
//scanf("%d", &x);
//    li = 1; ls = m; ga = 0;
//    while(li <= ls and ga == 0)
//    {
//      k = (li + ls) / 2;
//      if(a[1][k] == x) ga = 1;
//      else
//        if(x < a[1][k]) ls = k - 1;
//        else li = k + 1;
//    }
//    if (ga == 1) printf("%d",a[2][k], "%c");
//    else printf("%d",0, "%c");
//  }
//  return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("bare.in");
//ofstream fo("bare.out");
//int i,j,n,x,tr,k;
//int a[1000];
//string sir;
//int main()
//{
// fi>>n;
// fi.get();
// for(i=1;i<=5;i++)
//    {getline(fi,sir);
//
//     for(j=0;j<n;j++)
//       if(sir[j]=='.')a[j]=1;
//         else if(sir[j]=='X')a[j]=2;
//    }
//
//    while(1){
//     k=0;
//     for(i=0;i<n;i++)
//       if(a[i]==0)
//       {
//           if(i>=2){
//             if(a[i-1]==1 and a[i-2]==1){a[i]=2;k++;}
//             if(a[i-1]==2 and a[i-2]==2){a[i]=1;k++;}
//           }
//          if(i<=n-3){
//             if(a[i+1]==1 and a[i+2]==1){a[i]=2;k++;}
//             if(a[i+1]==2 and a[i+2]==2){a[i]=1;k++;}
//          }
//         if(i>=1){
//             if(a[i-1]==1 and a[i+1]==1){a[i]=2;k++;}
//             if(a[i-1]==2 and a[i+1]==2){a[i]=1;k++;}
//         }
//       }
//       if(k==0)break;
//    }
//    bool ok=true;;
//    for(i=0;i<n;i++)  if(a[i]==0)ok=false;
//    if(ok==false)fo<<"IMPOSIBIL";
//    else{
//            for(i=0;i<n;i++)
//            if(a[i]==a[i+1]){fo<<1;i++;}
//            else fo<<0;
//        }
// return 0;
//}

//#include <fstream>
//using namespace std;
//ifstream f("meteo1.in");
//ofstream g("meteo1.out");
//  int a[1001],s,i,n,k,j,maxi,pi,pf;
// int main()
//{
//   f>>n;
//   for(i=1;i<=n;i++)
//     f>>a[i];
//   k=1;
//   for(i=1;i<n;i++)
//       if((a[i]<0 and a[i+1]>=0) or (a[i]>=0 and a[i+1]<0))k++;
//       else {
//             if(k>=maxi){maxi=k;pi=i-k+1;pf=i;}
//             k=1;
//            }
//    if(k>=maxi){maxi=k;pi=i-k+1;pf=i;}
//    if(maxi>=2){
//           g<<maxi<<endl;
//            for(i=pi;i<=pf;i++)g<<a[i]<<" ";
//              }
//        else g<<0;
//   return 0;
//}
//#include <fstream>
//#include<cmath>
//#define M 60001
//using namespace std;
//ifstream f("factori.in");
//ofstream g("factori.out");
//int fr[2*M],n,i,j,p,t,x,y,pr[2*M],k;
//
//int main() {
//fr[1]=1;
//for(i=2;i<=M;i++)
// if(fr[i]==0){
// for(j=2*i;j<=M-1;j=j+i)fr[j]=1;
// }
//
//for(i=2;i<=M-1;i++)if(fr[i]==0){pr[++k]=i;}
//while(f>>y){
//  if(y==0)break;
//  for(i=1;i<=M-1;i++)fr[i]=0;
//  for(i=2;i<=y;i++){
//   t=1; x=i;
//   while(x!=1){
//       p=0;
//       while(x%pr[t]==0){p++;x/=pr[t];}
//       fr[pr[t]]+=p;
//       t++;
//    }
//  }
//
//  for(i=2;i<=M-1;i++)
//     if(fr[i]>0)g<<fr[i]<<' ';
//    g<<'\n';
//}
//
//  f.close();g.close();
//  return 0;
//}
//#include <iostream>
//using namespace std;
//int a[1001],b[1001],p,i,j,n,k,y,x,r;
//int main()
//{
//cin>>n;
//for(i=1;i<=n;i++)cin>>a[i];
//for(i=1;i<=n-1;i++)
//  {
//      x=a[i];y=a[n];
//      do{
//        r=x%y;
//        x=y;
//        y=r;
//      }while(r);
//      if(x==1)b[++p]=a[i];
//  }
//for(i=1;i<=p;i++)
// for(j=i+1;j<=p;j++)
//    if(b[i]<b[j])swap(b[i],b[j]);
//for(i=1;i<=p;i++)
//cout <<b[i]<< " ";
//return 0;
//}
//#include <iostream>
//using namespace std;
//
//long long s1,s2,s3,s,x,y,maxi,a[101],mini,k,n,i,gasit,aa;
//int main()
//{cin>>n;
//for(i=1;i<=n;i++)
//{
//cin>>s1>>s2;
//s=s+s1*s2;
//s3=s3+s1;
//}
//cout<<s<<" "<<(float)s/s3;
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream f("petrol.in");
//ofstream g("petrol.out");
//int n,eu,du,i,j;
//double maxi,e[101],d[101];
//int main()
//{
//    f>>n>>eu>>du;
//    for(i=1; i<=n; i++)
//        f>>e[i]>>d[i];
//    for(i=1; i<=n; i++)
//    {
//     e[i]=eu/e[i];
//     d[i]=du/d[i];
//    }
//    if(n!=1)
//    {for(i=1; i<=n; i++)
//    for(j=1; j<=n; j++)
//        if(i!=j)
//        maxi=max(maxi,e[i]+d[j]);
//    g<<maxi;
//    }
//    else g<<max(e[1],d[1]);
//
//    return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream f("bile6.in");
//ofstream g("bile6.out");
//bool c[2001][2001];
//int m,n,p,i,j,k,t,x,r,lin;
//int a[2001],b[2001];
//int main()
//{
//    f>>m>>n>>p;
//    for(t=1;t<=p;t++){
//        f>>i>>j;
//        c[i][j]=1;
//    }
//    for(i=1;i<=n;i++)  f>> a[i];
//
//    for(i=1;i<m;i++)
//    {
//         for(j=1;j<=n;j++)b[j]=0;
//
//         for(j=1;j<=n;j++)
//            if(c[i+1][j]==0)b[j]+=a[j];
//            else {
//                 b[j-1]+= (a[j]+1)/2;
//                 b[j+1]+= (a[j])/2;
//              }
//            for(j=1;j<=n;j++)a[j]=b[j];
//    }
//    for(j=1;j<=n;j++)
//        g<<b[j]<<'\n';
//        return 0;
//}

//#include <cstdio>
//#define Nmax 500003
//using namespace std;
//unsigned int a[Nmax];
//long long int k,i,x,y,N,L,M,p,l,d,s,maxi;
//int main()
//{
//    freopen("praslea.in","r",stdin);
//    freopen("praslea.out","w",stdout);
//    scanf("%lld%lld%lld",&N,&M,&L);
//    for(i=1;i<=N;i++)a[i]=L;
//    for(i=1;i<=M;i++)
//      {scanf("%lld%lld",&p,&l);a[p]=l;}
//    scanf("%lld",&d);
//    for(i=1;i<=N;i++)
//     if(a[i]==L)k++;
//      else {if(k>maxi)maxi=k;k=0;}
//   if(k>maxi)maxi=k;
//    printf("%lld\n",maxi);
//
// for(i=1;i<=N;i++)
// {
//  s+=a[i];
//  if(s>=d){printf("%lld\n",i);break;}
//  }
//return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream f("suma.in");
//ofstream g("suma.out");
//int n,i,x,nn,y,s,xx;
//int main()
//{
//    f>>n;
//    if(n==1)
//    g<<1<<'\n'<<1;
//    if(n<10 and n>1)
//    if(n==2){g<<11<<'\n'<<20;}
//    if(n==3){g<<102<<'\n'<<300;}
//    if(n==4){g<<1003<<'\n'<<4000;}
//    if(n==5){g<<10004<<'\n'<<50000;}
//    if(n==6){g<<100005<<'\n'<<600000;}
//    if(n==7){g<<1000006<<'\n'<<7000000;}
//    if(n==8){g<<10000007<<'\n'<<8000000;}
//    if(n==9){g<<100000008<<'\n'<<900000000;}
//    if(n==10){g<<1000000009<<'\n'<<9100000000;}
//    //
//    if(n<100 and n>10)
//    {
//        y=n/9;
//        if(n%9!=0)
//        x=n-9*y-1;
//        else {x=8;y--;}
//        xx=n-9*y;
//        g<<1;
//        for(i=1;i<=n-y-1-1;i++)
//        g<<0;
//        g<<x;
//        for(i=1;i<=y;i++)
//        g<<9;
//        g<<'\n';
//        for(i=1; i<=y; i++)
//        {
//            g<<9;
//        }
//        g<<xx;
//        for(i=1; i<=n-y-1; i++)
//            g<<0;
//    }
//    //
//    if(n<1000 and n>=100)
//    {y=n/9;
//        if(n%9!=0)
//        x=n-9*y-1;
//        else {x=8;y--;}
//        xx=n-9*y;
//    g<<1;
//    for(i=1;i<=n-y-1-1;i++)
//    g<<0;
//    g<<x;
//    for(i=1;i<=y-1;i++)
//g<<9;
//g<<'\n';
//for(i=1;i<=y;i++)
//g<<9;
//g<<xx;
//for(i=1;i<=n-y-2;i++)
//g<<0;
//    }
//    if(n==1000)
//    {y=n/9;xx=n-9*y;
//        if(n%9!=0)
//        x=n-9*y-1;
//
//        else {x=8;y--;}
//        g<<1;
//        for(i=1;i<=1000-112;i++)
//        g<<0;
//        for(i=1;i<=111;i++)
//        g<<9;
//        g<<'\n';
//        for(i=1;i<=111;i++)
//        g<<9;
//        g<<1;
//        for(i=1;i<=1000-112;i++)
//        g<<0;
//
//
//    }
//    return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("albine2.in");
//ofstream fo("albine2.out");
//int a,b,c,d,k1,L1,L2,ss,k2,t,n,m,dd;
//
//int main()
//{
//    fi>>n>>m;a=1;b=1;c=n;d=n;
//    for(t=1;t<=m;t++)
//        {
//            fi>>dd;
//            if(dd==0){a--;c--;}
//            if(dd==1){b++;d++;}
//            if(dd==2){a++;c++;}
//            if(dd==3){b--;d--;}
//            k1=max(1,b); k2=min(n,d);
//            if(k1<=k2)L1=k2-k1+1;
//            else L1=0;
//            k1=max(1,a); k2=min(n,c);
//            if(k1<=k2)L2=k2-k1+1;
//            else L2=0;
//            ss+=n*n-L1*L2;
//        }
//fo<<ss;
//
//
//    return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("cautanrinmatrice.in");
//ofstream fo("cautanrinmatrice.out");
//int a[1001][1001],i,j,n,m,p,b[1000001];
//int k,st,dr,mij,ok,x;
//int main(){
//  fi>>n>>m;
//  for(i=1;i<=n;i++)
//    for(j=1;j<=m;j++)  fi>>a[i][j];
//   for(i=1;i<=n;i++)  //se face b[] vector crescator din a
//    if(i%2==1)
//       for(j=1;j<=m;j++)  b[++k]=a[i][j];
//    else
//        for(j=m;j>=1;j--)  b[++k]=a[i][j];
//  fi>>p;
//  for(i=1;i<=p;i++)
//  {
//     fi>>x;
//     ok=0;  //cautare binara
//     st=1;dr=k;
//     while(st<=dr)
//     {
//         mij=(st+dr)/2;
//         if(x==b[mij]){ok=1;break;}
//         if(x<b[mij])dr=mij-1;
//         else st=mij+1;
//     }
//     int lin,col,poz=mij;
//     if(ok==1)  //afisare pozitii gasite
//     {
//         lin=(poz-1)/m+1;
//         col=(poz-1)%m+1;
//         if(lin%2==0)col=m-col+1; //ajustare pozitie pe linie
//         fo<<lin<<" "<<col<<'\n';
//
//     }
//     else fo<<0<<'\n';
//  }
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("pavare1.in");
//ofstream fo("pavare1.out");
//int v,i,j,n,m,x,d,s1,s2,k,sol,rest;
//int main()
//{
//   fi>>v>>n;
//   i=1;
//   while(n>=i){
//      if(2*i<=n){n=n-2*i;k=2;}//daca raman 2 valori maxime
//      else if(i<=n){n=n-i;k=1;}//daca ramane 1 valoare  maxima
//      i++;
//   }
//   i--;rest=n;
//   if(v==1){
//       if(k==2)sol=2*i;
//       else sol=2*(i-1)+1;
//       if(n)sol++;
//       fo<<sol;return 0;
//       }
//     if(v==2){
//       if(k==2){   //daca raman 2 valori maxime
//             m=i;
//             for(j=1;j<=m;j++)
//                  {fo<<j<<" ";
//                   if(j==rest)fo<<j<<" ";
//                  }
//             for(j=m;j>=1;j--)fo<<j<<" ";
//             }
//       if(k==1) {   //daca ramane 1 valoare  maxima
//             m=i;
//             for(j=1;j<=m;j++)
//                  {fo<<j<<" ";
//                   if(j==rest)fo<<j<<" ";
//                  }
//             for(j=m-1;j>=1;j--)fo<<j<<" ";
//             }
//       return 0;
//       }
//   return 0;
//}
//#include <fstream>
//#define M 5003
//using namespace std;
//ifstream fin("bosumflat.in");
//ofstream fout("bosumflat.out");
//int p,cif,i,j,x,y,n,k,xp,xi,yp,yi,f1,f2;
//int a[M],b[M],Xi[M],Xp[M];
//
//int main()
//{   fin>>n;
//    for(i=1;i<=n;i++)fin>>a[i];
//    for(i=1;i<=n;i++)
//        {
//           x=a[i];
//           f1=f2=1;
//           p=0;
//           xi=xp=0;
//           while(x){
//            p++;
//            cif=x%10;
//            if(p%2==1){xp+=cif*f1;f1*=10;}
//            else {xi+=cif*f2;f2*=10;}
//            x=x/10;
//           }
//           Xi[i]=xi;
//           Xp[i]=xp;
//        }
//
//    for(i=1;i<=n;i++)
//        for(j=i+1;j<=n;j++){
//          if(Xi[i]<Xp[j] and Xp[i]>Xi[j])b[i]++;
//          if(Xi[j]<Xp[i] and Xp[j]>Xi[i])b[j]++;
//        }
//    for(i=1;i<=n;i++)fout<<b[i]<<" ";
//    return 0;

//#include<fstream>
//#include<algorithm>
//using  namespace std;
//
//ifstream f("numere6.in");
//ofstream g("numere6.out");
//long long a,b,x[11],y[11],i,j;
//int main(){
//    f>>a>>b;
//    if(a>0 and b>0)
//    {while(a)
//    {
//        x[++i]=a%10;
//        a=a/10;
//    }
//    while(b)
//    {
//        x[++i]=b%10;
//        b=b/10;
//    }
//
//    sort(x+1,x+i+1);
//    for(j=i;j>=1;j--)
//    g<<x[j];
//    }
//    if(a>0 and b<1)
//    {
//       while(a)
//    {
//        x[++i]=a%10;
//        a=a/10;
//    }
//    sort(x+1,x+i+1);
//    for(j=i;j>=1;j--)
//    g<<x[j];g<<b;
//    }
//        if(b>0 and a<1)
//    {
//       while(b)
//    {
//        x[++i]=b%10;
//        b=b/10;
//    } g<<a;
//    sort(x+1,x+i+1);
//    for(j=i;j>=1;j--)
//    g<<x[j];
//    }
//    return 0;
//}
//#include<fstream>
//using  namespace std;
//
//ifstream f("imprimanta.in");
//ofstream g("imprimanta.out");
//long long i,n,k,mini=100,nrc,cif,sol,pct[10],a[100];
//int main(){
//    f>>n>>k;
//    pct[0]=12;pct[1]=5;pct[2]=11;pct[3]=11;pct[4]=9;
//    pct[5]=11;pct[6]=12;pct[7]=7;pct[8]=13;pct[9]=12;
//    while(n){
//      cif=n%10;
//      a[++nrc]=cif;
//      n=n/10;
//    }
//    for(i=1;i<=nrc;i++)
//       if(mini>pct[a[i]])mini=pct[a[i]];
//    for(i=1;i<=nrc;i++)
//       if(mini==pct[a[i]]&&sol<a[i])sol=a[i];
//    g<<sol<<'\n';
//
//    if(k%5==0) for(i=1;i<=k/5;i++)g<<1;
//    if(k%5==1) if(k==16)g<<"74";
//              else {g<<"777";for(i=1;i<=(k-21)/5;i++)g<<1;}
//    if(k%5==2) {g<<"71";for(i=1;i<=(k-12)/5;i++)g<<1;}
//    if(k%5==3) {g<<"8";for(i=1;i<=(k-13)/5;i++)g<<1;}
//    if(k%5==4) {g<<"77";for(i=1;i<=(k-14)/5;i++)g<<1;}
//    return 0;
//}
//#include <cstdio>
//using namespace std;
//int palme,n,k,i,x,fr[100001];
//int main(){
//    freopen("carti1.in","r",stdin);
//    freopen("carti1.out","w",stdout);
//    scanf("%d",&n);
//    for(i=1;i<=n;i++)
//     { scanf("%d",&x);
//       if(fr[x-1]==1){fr[x-1]=0;fr[x]=1;}
//        else fr[x]=1;
//     }
//    for(i=1;i<=n;i++)
//        if(fr[i]>0)palme++;
//
//    printf("%d\n",palme-1);
//    return 0;
//}
//#include <fstream>
//
//using namespace std;
//
//ifstream f("schi1.in");
//ofstream g("schi1.out");
//int n, a[3][100001], k, x, i, li, ls, ga,m,kk;
//int main()
//{
//  freopen("schi1.in", "r" ,stdin);
//  freopen("schi1.out", "w" ,stdout);
//  //scanf("%d", &n);
//  //printf("%d",n);
//  scanf("%d", &n); k = 0;
//  for(i = 1; i <= n; i++)
//  {
//    //f >> x;
//    scanf("%d", &x);
//    if(x > a[1][k])
//    { k++;
//      a[1][k] = x;
//      a[2][k] = 1;
//    }
//    else
//    { if(k == 0)k++;
//    a[2][k]++;
//    }
//  }
//  m=k;
// // f >> kk;
// scanf("%d", &kk);
//  for(i=1;i<=kk;i++) {
//
//scanf("%d", &x);
//    li = 1; ls = m; ga = 0;
//    while(li <= ls and ga == 0)
//    {
//      k = (li + ls) / 2;
//      if(a[1][k] == x) ga = 1;
//      else
//        if(x < a[1][k]) ls = k - 1;
//        else li = k + 1;
//    }
//    if (ga == 1) printf("%d",a[2][k], "%c");
//    else printf("%d",0, "%c");
//  }
//  return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long k,s,j,n,i,a,x,b,mini,maxi;
//char c;
//int main()
//{while(cin>>a and a!=0)
//if(a%2==1)k++;
//cout<<k;
//
// return 0;
//}
//#include <fstream>
//
//using namespace std;
//
//ifstream f("greieri.in");
//ofstream g("greieri.out");
//long long q,k,n,m,i,na,r,p;
//int a[100001];
//int main()
//{
//    f>>n>>m;
//   p=n*(n-1);
//   g<<p<<'\n';
//   r=m%p;
//    k=r/(n-1);
//    for(i=n-k+1;i<=n;i++)
//    a[++na]=i;
//    for(i=1;i<=n-k;i++)a[++na]=i;
//    q=r%(n-1);
//    for(i=n;i>=n-q+1;i--)
//    swap(a[i], a[i-1]);
//    for(i=1;i<=na;i++)
//    g<<a[i]<<" ";
//return 0;
//}
//#include <iostream>
//using namespace std;
//int maxi, a[251][251], n, m, i, j,k;
//int main()
//{ cin>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// {
//     cin>>a[i][j];
// }
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// {
//     if(a[i][j]==1 and a[i-1][j]==0 and a[i][j-1]==0)
//       k++;
// }
// cout<<k<<" ";
//
// return 0;
//}
//#include <fstream>
//#define Nmax 200001
//using namespace std;
//ifstream f("lightbot.in");
//ofstream g("lightbot.out");
//int maxi,x,m,d,c,k,p,i,n,a[2*Nmax];
//int main()
//{
//    int fr[Nmax]={0};
//    f>>c>>n;
//    while(f>>x)a[++m]=x,fr[a[m]]++;
//    if(c==1)
//    {
//        k=0;
//        for(i=1; i<m; i++)
//        {
//            d=a[i+1]-a[i];
//            if(d<0)d=-d;
//            if(d!=1)k++;
//        }
//        g<<(k+1)/2;
//    }
//    if(c==2){
//        maxi=0;
//        for(i=1;i<Nmax;i++)
//            maxi=max(maxi,fr[i]);
//        for(i=Nmax-1;i>=1;i--)
//            if(maxi==fr[i])break;
//        g<<i;
//    }
//    if(c==3)
//    {
//        k=0;
//        for(i=1; i<m; i++)
//        {
//            d=a[i+1]-a[i];
//            if(d<0)d=-d;
//            if(d!=1){k++;if(k%2==1)g<<a[i]+1<<" ";}
//        }
//    }
//    return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream f("pluton.in");
//ofstream g("pluton.out");
//int a[40001],i,j,n,k,poz,s,el,ok,pi,pj,elsol,ii,jj,f1[10],f2[10];
//int main()
//{
//    f>>n;
//    for(i=1; i<=n; i++)
//        f>>a[i];
//    for(i=1; i<=n; i++)
//        for(j=i+1; j<=n; j++)
//        {while(a[i])
//        f1[a[i]%10]++;
//        a[i]=a[i]/10;
//        while(a[i])
//        f2[a[j]%10]++;
//        a[j]=a[j]/10;
//        for(i=1;i<=9;i++)
//        if(f1[i]==f2[i])k++;
//
//        }g<<k;
//        return 0;
//}
//#
//#include<fstream>
//using namespace std;
//ifstream f("renju.in");
//ofstream g("renju.out");
//int a[25][25],i,j,n,k,poz,s,el,ok,pi,pj,elsol,ii,jj;
//int main(){
//    for(i=1;i<=19;i++)
//    for(j=1;j<=19;j++)
//    f>>a[i][j];
//    for(i=1;i<=19 and ok==0;i++)
//    for(j=1;j<=19 and ok==0;j++)
//    if(a[i][j]!=0){
//    el=a[i][j];
//    if(a[i][j-1]!=el){
//        jj=j;k=0;while(a[i][jj]==el)jj++,k++;
//        if(k==5){pi=i; pj=j;elsol=el; ok=1;}
//
//         }
//
//    if(a[i-1][j]!=el){
//        ii=i;k=0;while(a[ii][j]==el)ii++,k++;
//        if(k==5){pi=i; pj=j;elsol=el; ok=1;}
//
//         }
//         if(a[i-1][j-1]!=el){
//        ii=i;jj=j;k=0;while(a[ii][jj]==el)ii++,jj++,k++;
//        if(k==5){pi=i; pj=j;elsol=el; ok=1;}
//
//         }
//         if(a[i-1][j+1]!=el){
//        ii=i;jj=j;k=0;while(a[ii][jj]==el)ii++,jj--,k++;
//        if(k==5){pi=ii-1; pj=jj+1;elsol=el; ok=1;}
//
//         }
//    }
//  if(elsol!=0)  g<<elsol<<'\n'<<pi<<' '<<pj;
//else
//g<<0;
//return 0;
//}
//#include<fstream>
//#include<iostream>
//using namespace std;
//ifstream f("roboti1.in");
//ofstream g("roboti1.out");
//struct robot{
//  int i,j;
//  char d;
//  int ok;
//};
//int dir,fr[51][51],a[51][51],p,q,i,n,m,k,t,comanda;
//int maxi,pi,pj,w,z,j;
//char b[51][51];
//robot r[100];
//int main(){
//   f>>p>>q;
//   f>>n;
//   for(k=1;k<=n;k++){f>>r[k].i>>r[k].j>>r[k].d;fr[r[k].i][r[k].j]=1;}
//   f>>m;
//   for(k=1;k<=n;k++)f>>b[k];
//
//  for(k=1;k<=m;k++){
//     for(t=1;t<=n;t++)
//        if(r[t].ok==0)
//        {
//          comanda=b[t][k-1];
//          if(comanda=='F'){
//             if(r[t].d=='N')r[t].i--;
//             if(r[t].d=='S')r[t].i++;
//             if(r[t].d=='E')r[t].j++;
//             if(r[t].d=='V')r[t].j--;
//                 fr[r[t].i][r[t].j]++;
//           }
//           if(comanda=='R'){
//               if(r[t].d=='N')r[t].d='E';
//               else if(r[t].d=='E')r[t].d='S';
//               else if(r[t].d=='S')r[t].d='V';
//               else if(r[t].d=='V')r[t].d='N';
//              }
//            if(comanda=='L'){
//               if(r[t].d=='N')r[t].d='V';
//               else if(r[t].d=='V')r[t].d='S';
//               else if(r[t].d=='S')r[t].d='E';
//               else if(r[t].d=='E')r[t].d='N';
//              }
//        }
//      for(t=1;t<=n;t++)
//       if(r[t].ok==0)
//        {
//         if(r[t].i==0 or r[t].j==0 or r[t].i==p+1 or r[t].j==q+1)
//                    r[t].ok=1;
//         w=0;
//         for(z=1;z<=n;z++)
//                   if(r[t].i==r[z].i and r[t].j==r[z].j and r[z].ok==0) w++;
//         if(w>1)
//             for(z=1;z<=n;z++)
//                if(r[t].i==r[z].i and r[t].j==r[z].j and r[z].ok==0)
//                       r[z].ok=1;
//        }
//
//  }
//  w=0;
//  for(t=1;t<=n;t++)
//    if(r[t].ok==0)w++;
//  g<<w<<'\n';
//  for(i=1;i<=p;i++)
//    for(j=1;j<=q;j++)
//      if(fr[i][j]>maxi){maxi=fr[i][j];pi=i;pj=j; }
//  g<<pi<<" "<<pj<<" "<<maxi;
//
//   return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long k,s,j,n,i,a,x,b,mini,maxi;
//char c;
//int main()
//{cin>>n>>a;mini=a;
//for(i=2;i<=n;i++)
//{cin>>a;
//    if(mini>a)mini=a;
//    if(maxi<a)maxi=a;
//}
//cout<<maxi+mini;
// return 0;
//}
//#include <fstream>
//
//using namespace std;
//ifstream f("n_suma.in");
//ofstream g("n_suma.out");
//int a,s,i,n;
//
//int main()
//{
//    f>>n;
//  for(i=1;i<=n;i++)
//  {
//    f>>a;
//    s=s+a;
//  }
//
//  g<<s;
//    return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream f("sume4.in");
//ofstream g("sume4.out");
//long long j,c,k,s,n,i,a[100001],x,b,mini,maxi,y,z,s1,s2;
//int main()
//{f>>n;
//for(i=1;i<=n;i++)
//f>>a[i];
//for(i=1;i<=n;i++)
//{
//    x=a[i]%100;
//    y=a[i]/1000;
//    z=a[i]/100%10;
//    if(x>y or y>x)
//    {if(y>x)x=x+z;
//     if(x>y)y=y+z;
//    }
//    if(x==y)z=0;
//    s1=s1+x;
//    s2=s2+y;
//}
//g<<s2<<" "<<s1;
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream f("max_suma.in");
//ofstream g("max_suma.out");
//int b,d,k,p,t,i,aa,bb,n,x,m,j;
//int a[1001];
//int main()
//{f>>n;
//
//return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream f("2prim.in");
//ofstream g("2prim.out");
//int b,d,k,p,t,i,aa,bb,n,x;
//int a[1001];
//int main()
//{f>>n;
//for(i=1;i<=n;i++)
//f>>a[i];
//for(i=1;i<=n;i++)
//{x=a[i]%100;k=0;
//for(d=1;d<=x;d++)
//if(x%d==0)k++;
//if(k==2)b++;
//}
//g<<b;
//return 0;
//}
//#include <iostream>
//#include <cmath>
//using namespace std;
//long long j,c,k,s,n,i,a,x,b,mini,maxi;
//int main()
//{cin>>n;
//
//for(i=1;i<=n;i++)
//{
//    if(n%i==0 and i%2==1)
//    s=s+i;
//}
//cout<<s;
//return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long n,i,a,x,b,mini,maxi;
//
//int main()
//{cin>>n;maxi=-33;
//for(i=1;i<=n;i++)
//{   cin>>a;
//    if(a>=maxi)maxi=a;
//}
//cout<<maxi;
// return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long c,k,s,n,i,a,x,b,mini,maxi;
//float m;
//int main()
//{cin>>a>>b>>c;
//a=a*60;
//k=a+b+c;
//x=k/60;
//n=k%60;
//if(x>=24)
//x=x-24;
//if(n<=9)
//cout<<x<<' '<<0<<n;
//else cout<<x<<' '<<n;
//return 0;
//}
//var  b:array[1..200] of integer;
//  i,n,m,j,k,x,p,numar_f,numar_b,dif:longint;
//  f,g:text; ok:boolean;
//  sir:string;
//begin
//assign(f,'grupe1.in');reset(f);
//assign(g,'grupe1.out');rewrite(g);
//readln(f,n,k);
//readln(f,sir);
//ok:=true;
//for i:=1 to k  do
//  begin
//    read(f,m);p:=p+1;b[p]:=m;
//    numar_f:=0;numar_b:=0;
//    for j:=1 to m do
//                begin
//                read(f,x);
//                if sir[x]='f' then inc(numar_f);
//                if sir[x]='b' then inc(numar_b);
//                end;
//
//    dif:=numar_b-numar_f;
//    if dif<0 then dif:=-dif;
//    if(dif>1)then ok:=false;
//    writeln(g,numar_b,' ',numar_f);
//  end;
//for i:=1 to p do
// for j:=i+1 to p do
//    if(b[i]-b[j]>1)or(b[j]-b[i]>1)then ok:=false;
//if(ok=true)then writeln(g,'DA')
//    else writeln(g,'NU');
//close(f);close(g);
//end.
//#include<stdio.h>
//#include<algorithm>
//using namespace std;
//long a[100001],b[100001],i,n,j,k,t; long long s;
//int main()
//{
//    freopen("deal.in","r",stdin);
//    freopen("deal.out","w",stdout);
//    scanf("%ld",&n);
//    for(i=1;i<=n;i++)scanf("%ld",&a[i]);
//    sort(a+1,a+n+1);
//    i=1;j=n;
//    while(i<j && a[i]!=a[j]){
//     s+=a[j];
//     b[++t]=a[i];b[++t]=a[j];
//     i++;j--;
//    }
//    if(i<j&&a[j]>b[1]){s+=a[j];i++;j--;}
//    if(i<j&&a[j]<b[t]){s+=a[j];i++;j--;}
//    k=2;
//    while(i<j&&k<t){
//              if(b[k]>a[j]&&b[k+1]<a[j])
//                                {s+=a[j];i++;j--;}
//              k+=2;
//    }
//    if(i==1&&j==n)s=1;
//   printf("%lld\n",s);
//   return 0;
//}
//#include <fstream>
//#define M 40001
//using namespace std;
//ifstream f("celule.in");
//ofstream g("celule.out");
//int a,b,d,k,p,t,i,aa,bb;
//int fa[M],fb[M];
//int main()
//{
//    f>>a>>b;aa=a;bb=b;
//    d=2;
//    while(a!=1 and d*d<=aa)
//    {
//        p=0;
//        while(a%d==0){p++;a=a/d;}
//        fa[d]+=p;
//        d++;
//    }
//
//    d=2;
//    while(b!=1 and d*d<=bb)
//    {
//        p=0;
//        while(b%d==0){p++;b=b/d;}
//        fb[d]+=p;
//        d++;
//    }
//   if(a<M){fa[a]++;a=1;}
//   if(b<M){fb[b]++;b=1;}
//
//    for(i=2;i<=M-1;i++)
//      {int  r=fa[i]-fb[i];
//       if(r>0)k+=r;
//       else k+=-r;
//      }
//
//   if(a==1 and b!=1)k++;
//   if(a!=1 and b==1)k++;
//   if(a!=1 and b!=1 and a!=b)k+=2;
// g<<k<<endl;
// //for(i=1;i<=20;i++)g<<
//return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long s,n,i,a,x,b,mini,maxi;
//
//int main()
//{cin>>a>>b;
//for(i=1;i<=n;i++)
//{
//    x=b %i;
//    s=s+x;
//}
//cout<<s;
// return 0;
//}
//#include <fstream>
//
//using namespace std;
//ifstream f("sum.in");
//ofstream g("sum.out");
//long long a,x,b,mini,maxi;
//
//int main()
//{f>>a>>b;
//g<<a+b;
// return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long a,x,b,mini,maxi;
//
//int main()
//{cin>>a>>b>>x;
//mini=100000000001;
//maxi=-1;
//if(mini>a)mini=a;
//if(mini>b)mini=b;
//if(mini>x)mini=x;
//if(maxi<a)maxi=a;
//if(maxi<b)maxi=b;
//if(maxi<x)maxi=x;
//cout<<maxi-mini;
// return 0;
//}

//#include <iostream>
//
//using namespace std;
//long long a,x,b;
//
//int main()
//{cin>>a;
//while(a)
//{
//    x=a%10;
//    if(x%2==1)b++;
//    a=a/10;
//}
//cout<<b;
// return 0;
//}

//#include <iostream>
//
//using namespace std;
//long long a,x,b;
//
//int main()
//{cin>>a>>b;
//if(a!=b)
//{if(a>b)
//
//cout<<"Primul copil este mai mare cu"<<" "<<a-b<<" "<<"ani";
//else cout<<"Al doilea copil este mai mare cu"<<" "<<b-a<<" "<<"ani";
//}
//else cout<<"Copiii au varste egale";
// return 0;
//}
//
//#include <iostream>
//
//using namespace std;
//long long c,a,x,b,mini;
//
//int main()
//{cin>>a>>b>>c;
//mini= 1000000001;
//if(a<mini)mini=a;
//if(b<mini)mini=b;
//if(c<mini)mini=c;
//
//cout<<mini;
//
// return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long a,x,b;
//
//int main()
//{cin>>a>>b;
//if(a>b)
//cout<<a;
//else cout << b;
//
// return 0;
//}

//#include <iostream>
//
//using namespace std;
//long long a,x,b;
//
//int main()
//{cin>>a>>b>>x;
//if(a<=x and b>=x)
//cout<<"DA";
//else cout<<"NU";
// return 0;
//}
//#include <iostream>
//
//using namespace std;
//int s,x,y;
//
//int main()
//{cin>>x;
//if(x>=5)
//cout<<"promovat";
//else cout << "corigent";
// return 0;
//}
//#include <iostream>
//
//using namespace std;
//int s,x,y;
//
//int main()
//{cin>>x>>y;
//s=y/x;
//if(y%x==0)cout<<s;
//else cout<<s+1;
// return 0;
//}
//#include <iostream>
//
//using namespace std;
//int cif,s,n,i;
//long long nr;
//int main()
//{cin>>n;
//nr=1;
//for(i=1;i<=n;i++)
//{
//    nr=nr*i;
//}
//
//cout<<nr;
//
// return 0;
//}
//#include <iostream
//#include <cmath>
//using namespace std;
//int nr,cif,s;
//int main()
//{cin>>nr;
//s=sqrt(nr);
//
//cout<<s;
//
// return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//int nr,cif,s;
//int main()
//{cin>>nr;
//
//
//    cif=nr%100;
//    s=cif%10;
//    cif=cif/10;
//    s=s+cif;
//
//cout<<s;
//
// return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//int c,l,h;
//int main()
//{cin>>l>>h;
//c=h/l;
//cout<<c;
//
// return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//int ga,gg,gr,s;
//int main()
//{cin>>ga;
//gr=2*ga;
//gg=gr-3;
//s=gr+gg+ga;
//cout<<s;
//
// return 0;
//}
//#include <fstream>
//#include <iostream>
//using namespace std;
//int n,k;
//int main()
//{
// while(cin>>n)
// if(n==0)
// {if (k==0)
// cout<<"NU EXISTA";
// else
// cout<<k;}
// else {if(n%2==0)k++;}
// }
// if (k==0)
// cout<<"NU EXISTA";
// else
// cout<<k;
// return 0;
//}
//#include <fstream>
//
//using namespace std;
//ifstream f("maxmat.in");
//ofstream g("maxmat.out");
//int maxi, a[26][26], n, m, i, j,k;
//int main()
//{
// f >> n >> m;
// for(i = 1; i <= n; i++)
//   for(j = 1; j <= m; j++)
//     f >> a[i][j];
// for(i = 1; i <= n; i++)
// { maxi = -1001;
//   for(j = 1; j <= m; j++)if(a[i][j] >= maxi)maxi = a[i][j],k=j; g << maxi << " " << k; g << '\n';
// }
// return 0;
//}
//#include<iostream>
//using namespace std;
//int v[1001],s,j,k,n,i,x,d;
//int main()
//{
//    cin>>n;
//    for(i=2;i<=n;i++)
//    {
//        x=i;d=2;
//        while(x!=1){
//            while(x%d==0){v[d]++;x=x/d;}
//            d++;
//        }
//    }
//     v[2]-=v[5];
//     v[5]=0;
//     s=1;
//     for(i=1;i<=1000;i++)
//        for(j=1;j<=v[i];j++)
//          s=(s*i)%10;
//     cout<<s;
//     return 0;
//}
//#include <iostream>
//
//using namespace std;
//long long n,i;;
//int main()
//{    cin>>n;
//;
//for(i=1;i<=n;i++)
//{
//    cout<<2*i<<" ";
//}
//    return 0;
//}

//#include <iostream>
//
//using namespace std;
//long long a,b,s,x,ucif;
//int main()
//{    cin>>a>>b;
//s=a+b;
//cout<<s%10;
//    return 0;
//}

//#include <iostream>
//
//using namespace std;
//long long a,b;
//int main()
//{    cin>>a>>b;
//cout<<a+b<<' ';
//if(a>b)
//cout<<a-b<<' ';
//else
//cout<<b-a<<' ';
//cout<<a*b<<' ';
//cout<<a/b;
//    return 0;
//}

//#include <iostream>
//
//using namespace std;
//long long a,b;
//int main()
//{    cin>>a>>b;
//if(a>b)
//cout<<a-b;
//else
//cout<<b-a;
//    return 0;
//}
//
//#include <iostream>
//
//using namespace std;
//long long a,b;
//int main()
//{    cin>>a>>b;
//   cout<<a+b;
//    return 0;
//}