#include<bits/stdc++.h>
#include<cstring>
#include <cctype>
#include <stdio.h>
#include <string.h>
using namespace std;
ifstream fin("citire.in");
ofstream fout("afisare.out");

void count(float a[],int n)
{
    float suma = 0;
    int i;
    for(i=1;i<=n;i++)
        suma = suma + a[i];
    float m = suma / n;
    int cnt = 0;
    for(i=1;i<=n;i++)
    {
        if(a[i] >= m)
            cnt++;
    }
    fout<<suma<<" "<<m<<" "<<cnt;
}


void radical(int n,int &x,int &y)
{
    x=1,y=1;
    int div = 2;
    while(n>1)
    {
        int exp = 0;
        while(n%div==0)
        {
            exp++;
            n=n/div;
        }
        if(exp)
        {
            if(exp%2==0)
            {
                x=x*pow(div,exp/2);
            }
            else{
                y=y*div;
                exp--;
                if(exp)
                {
                    x=x*pow(div,exp/2);
                }
            }
        }
        div++;
    }
}

void simulare_2018_s3_4()
{
    int x, y,okx,oky,a;
    okx=oky=1;
    fin >> x >> y;
    if(x > y)
    {
        a=x;
        x=y;
        y=a;
    }

    int z;
    while(fin>>z)
    {
        if(z > x && okx)
        {
            if(z > y && oky)
            {
                fout << x <<" "<< y <<" "<< z<<" ";
                okx = 0;
                oky = 0;
            }
            else
            {
                fout << x <<" "<< z<<" ";
                okx = 0;
            }
        }
        else if(z > y && !okx && oky)
        {
            fout << y <<" "<< z<<" ";
            oky = 0;
        }
        else
            fout << z<<" ";
    }
    if(okx)
        fout << x;
    if(oky)
        fout << y;

}

int Egal(long n)
{
    unsigned int c,ci=0;
    while(n)
    {
        c=n%10;
        if(c%2==1 && ci == 0)
        {
            ci=c;
        }
        if(c%2==1 && ci!=0 && ci!=c)
            return 0;
        n=n/10;
    }
    return 1;
}

void v1_2019_s3_2()
{
    char c[101],*p;
    int n,ok=0;
    cin.getline(c,100);
    cin>>n;
    p=strtok(c," ");
    while(p!=NULL)
    {
        if(strlen(p) == n)
        {
            fout<<p<<'\n';
            ok=1;
        }
        p=strtok(NULL," ");
    }
    if(ok==0)
        fout<<"nu exista";
}

void v1_2019_s3_3()
{
    long n,x,y,z,i;
    cin>>n;
    cin>>x>>y>>z;
    for(i=n;i>=4;i--)
    {
        if(i%2==0)
            fout<<(i/2-1)*z-(i/2-1)*x+y<<" ";
        else fout<<(i/2)*z-(i/2-1)*x<<" ";
    }
    fout<<z<<" "<<y<<" "<<x;
    fout.close();
}

void s3_2_2019()
{
    unsigned int n, mat[21][21], i, j, p;
    cin>>n;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>mat[i][j];
        }
    }

    p = mat[0][0];
    int ok=0;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<i;j++)
        {
            if(mat[j][i-1]!=p || mat[i-1][j]!=p)
                ok=i-1;
        }
        if(ok)
            break;
    }
    fout<<ok; 
}

struct punct
{
    int x,y;
    char nume[10];
}e1,e2;

int adj[1001][1001],n,m,k;

void read()
{
    fin>>n>>m>>k;
    int i,x,y;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        adj[x][y] = adj[y][x] = 1;
        adj[x][0]++;
        adj[y][0]++;
    }
}

void solve()
{
    int ok=1;
    while(1)
    {
        ok=0;
        for(int i=1;i<=n;i++)
        {
            if(adj[i][0] > k && adj[i][0] != 0)
            {
                adj[i][0] = 0;
                for(int j=1;j<=n;j++)
                {
                    if(adj[i][j] == 1)
                    {
                        adj[i][j] = adj[j][i] = 0;
                        adj[j][0]--;
                    }
                }
                ok++;
            }
        }
        if(!ok)
            break;
    }
}

void afisare()
{
    int cnt = 0;
    for(int i=1;i<=n;i++)
    {
        if(adj[i][0] > 0)
            cnt++;
    }
    fout<<cnt<<'\n';
    for(int i=1;i<=n;i++)
    {
        if(adj[i][0] > 0)
            fout<<i<<" ";
    }
}

void shift(int n,int x[])
{
    int i,p=x[1];
    for(i=1;i<n;i++)
        x[i]=x[i+1];
    x[n]=p;
}

void total(int n)
{
    int sum = 0,k=0;
        for(int i=1;i<=n;i++)
        {
            sum = sum+(i%7+k);
            fout<<i%7+k<<" ";
            if(i%7==0)
                k = k+1;
        }

}

void Impare(long &n)
{
    long p=1,x,rez=0;
    x=n;
    while(x>9)
    {
        p*=10;
        x/10;
    }
    while(p)
    {
        short c=x/p%10;
        if(c%2==1)
            rez=rez*10+c-1;
        else 
            rez=rez*10+c;
        x=x%p;
        p=p/10;
    }
    n=rez;
}

void varianta4_sub3_3_2019()
{
    int n,contor=1,p=0,maxi=-1,ant=0;
    while(fin>>n)
    {
        if(n>maxi || (n==ant && maxi == n && p==contor-1))
        {
            maxi = n;
            p=contor;
            fout<<n<<" ";
        }
        ant=n;
        contor++;
    }
}

long cmmdc(long a,long b)
{
    if(a==0)
        return b;
    return cmmdc(b,a%b);
}

long frecventa[11];
void subiect2019_5vara_s3_3()
{
    long x;
    int cnt = 0;
    while(!fin.eof())
    {
        fin>>x;
        cnt++;
        while(x)
        {
            if(frecventa[x%10]== (cnt--))
                frecventa[x%10]++;
            x=x/10;
        }
    }
    int ok=0;
    for(int i=9;i>=0&&ok==0;i--)
    {
        if(frecventa[i]>=cnt)
        {
            fout<<i;
            ok=1;
        }
    }
    if(ok==0)
        fout<<"nu exista";
}
long frv[101];
void model2019_s3_3()
{
    long x,i;
    while(fin>>x)
        frv[x]++;
    long l=0,l_m=0;
    for(i=0;i<=100;i++)
    {
        if(frv[i]==0)
            l=0;
        else l=l+frv[i];
        if(l>l_m)
            l_m=l;
    }
    fout<<l_m;
    fin.close();
}

void inserare(long &n)
{
    long x,aux;
    x=aux=0;
    while(n>9)
    {
        short c=n%10;
        short c1=n/10%10;
        x=x*100+c*10+abs(c-c1);
        n=n/10;
    }
    x=x*10+n;
    while(x)
    {
        aux=aux*10+x%10;
        x=x/10;
    }
}

void simulare2019_s3_2()
{
    char s[51],*p;
    cin.getline(s,50);
    int k=0;
    char sir[4][50]={"COLEGIUL","NATIONAL","TEORETIC","LICEUL"};
    char rez[201];
    rez[0]='\0';
    p=strtok(s," ");
    while(p!=NULL)
    {
        if(p[strlen(p)-1]=='.')
        {
            p[strlen(p)-1]='\0';
            for(int i=0;i<=3;i++)
            {
                if(strstr(sir[i],p))
                {
                    strcat(rez,sir[i]);
                }
            }
        }
        else strcat(rez,p);
        p=strtok(NULL," ");
    }
    fout<<rez;
}

long mini(long a,long b)
{
    return a<b?a:b;
}
long maxi(long a,long b)
{
    return a>b?a:b;
}

void simulare2019_s3_3()
{
    long n,x,m1p,m1i,m2p,m2i,i;
    fin>>n;
    m1p=m1i=-1;
    m2i=m2p=INT_MAX;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        if(x%2==0)
            m1p=maxi(m1p,x);
        else m1i=maxi(m1i,x);
    }
    for(i=n+1;i<=2*n;i++)
    {
        fin>>x;
        if(x%2==0)
            m2p=mini(m2p,x);
        else m2i=mini(m2i,x);
    }
    if(m1p<m2i && m1i<m2p || m1i+m2i == INT_MAX-1 || m1p+m2p == INT_MAX-1)
        fout<<"DA";
    else fout<<"NU";
    fin.close();
}

void iarna2019_s3_2()
{
    char s[256],c[31],*p;
    cin.getline(s,255);
    cin>>c;
    p=strtok(s," ");
    int i,ok=0,pozitie;
    for(i=strlen(c)-1;i>=0 && ok==0;i--)
    {
        if(strchr("aeiou",c[i])!=NULL)
        {
            ok=1;
            pozitie = strlen(c)-i;
        }
    }
    if(ok==0)
        fout<<"NU EXISTA";
    else{
        ok=0;
        while(p!=NULL)
        {
            if(strcmp(p+strlen(p)-pozitie,c+strlen(c)-pozitie)==0)
            {
                fout<<p<<'\n';
                ok=1;
            }
            p=strtok(NULL," ");
        }
        if(ok==0)
            fout<<"NU EXISTA";
    }
}

void iarna2019_s3_3()
{
    long n,i,mij,par,k,x;
    par=mij=-1;
    k=0;
    fin>>n;
    while(fin>>x)
        frecventa[x]++;
    for(i=1;i<=9;i++)
    {
        if(i%2==0 && frecventa[i]>1)
        {
            par=i;
        }
        if(frecventa[i]%2==1)
        {
            k++;
            mij=i;
        }
    }
    if(n%2 == 0 && k>0 || k>1 && n%2 == 1 || par == -1)
        fout<<-1;
    else{
        fout<<par;
        frecventa[par]=frecventa[par]-2;
        for(i=9;i>=1;i--)
        {
            for(int j=1;j<=frecventa[i]/2;j++)
                fout<<i;
        }
        if(mij!=1)
            fout<<mij;
        for(i=1;i<=9;i++)
        {
            for(int j=1;j<=frecventa[i]/2;j++)
                fout<<i;
        }
        fout<<par;
    }
}

long multiplu(int n)
{
    long r = 0 , t;
    do
    {
        r += n;
        t = sqrt(r);
    }
    while(t * t != r);
    return r;
}


void varianta2_2020_s3_2()
{
    char text[101],*p;
    int x;
    fin.getline(text,100);
    p=strchr(text,'<');
    while(p!=NULL)
    {
        x=strchr(p,'>')-p;
        for(int i=1;i<x;i++)
            if(p[i]!=' ')
                p[i]=p[i]-32;
        p=strchr(p+1,'<');
    }
    fout<<text;
}

void varianta2_2020_s3_3()
{
    long x,y,z,mini,maxi;
    int ok = 0;
    mini=INT_MAX;
    maxi = -1;
    fin>>x>>y;
    while(fin>>z)
    {
        if(abs(x-z) <= mini && x<y && y>z)
        {
            mini = abs(x-z);
            if(y>maxi)
                maxi=y;
            ok = 1;
        }
        x=y;
        y=z;
    }
    if(ok)
        fout<<maxi;
    else fout<<"nu exista";
    fin.close();
}

long kpn(long a , long b , long k)
{
    long cnt = 0;
    for(long i = a ; i <= b ; i ++)
    {
        long s = 0;
        for(long d = 1 ; d * d <= i ; d ++ )
            if(i % d == 0)
            {
                s += d;
                if(d * d < i)
                    s += i / d;
            }
        if(i % 2 == s % 2)
            cnt ++;
        if(cnt == k)
            return i;
    }
    return -1;
}

void varianta5_2020_s3_2()
{
    char c[101],x[101],aux[101];
    cin.getline(c,100);
    char *p;
    x[0] = '\0';
    int i,ok=0;
    p=strtok(c," ");
    while(p!=NULL)
    {
        if(strlen(p)%2==1)
        {
            int l = strlen(p)-1;
            for(i=0;i<strlen(p);i++)
            {
                aux[i] = p[l];
                l--;
            }
            aux[i]='\0';
            if(strcmp(p,aux)!=0)
            {
                ok=1;
                strcat(x,aux);
            }
        }
        else{
            strcat(x,p);
        }
        strcat(x," ");
        p=strtok(NULL," ");
    }
    x[strlen(x)-1]='\0';
    strcpy(c,x);
    if(ok==1)
        fout<<c;
    else fout<<"nu exista";
}

void varianta5_2020_s3_3()
{
    long x,min_value,max_value;
    min_value = 101;
    max_value=8;
    while(fin>>x)
    {
        if(x>9 && x<100)
        {
            if(x>max_value)
                max_value = x;
            if(x<min_value)
                min_value = x;
        }
    }
    if(min_value-1<9 || max_value+1 >100)
        fout<<"nu exista";
    else fout<<min_value-1<<" "<<max_value+1;
}

void varianta6_2020_s3_2()
{
    char c[101],x[101];
    cin.getline(c,100);
    char *p;
    x[0] = '\0';
    int i,ok=0;
    p=strtok(c," ");
    while(p!=NULL)
    {
        if(strlen(p)>=3)
        {
            char car = p[0];
            for(i=0;i<strlen(p)-1;i++)
            {
                p[i]=p[i+1];
            }
            p[strlen(p)-1]=car;
            strcat(x,p);
            ok=1;
        }
        else{
            strcat(x,p);
        }
        strcat(x," ");
        p=strtok(NULL," ");
    }
    x[strlen(x)-1]='\0';
    strcpy(c,x);
    if(ok==1)
        fout<<c;
    else fout<<"nu exista";
}
long fr[1001];
void varianta6_2020_s3_3()
{
    long x,n=0;
    while (fin>>x)
    {
        fr[x]++;
        n++;
    }
    int impar=0;
    for(int i=1;i<=1000;i++)
    {
        if(fr[i]%2==1)
        {
            impar++;
        }
    }
    if(n%2==0&&impar>0 || n%2==1&&impar>1)
        fout<<"NU";
    else fout<<"DA";
    
}

void duplicare(long n, long &d)
{
    int gasit=0;
    long rez = 0;
    long x=n,p=1;
    while(x>9)
    {
        x=x/10;
        p=p*10;
    }
    while(p)
    {
        short c = n/p%10;
        if(c%2 == 1)
        {
            gasit=1;
            rez=rez*100+c*10+c;
        }
        else{
            rez=rez*10+c;
        }
        p=p/10;
    }
    if(gasit==1)
        d=rez;
    else d=-1;
}

void model2020_s3_2()
{
    char c[101],x[101],y[101],*p;
    int n;
    cin>>n;
    cin.get();
    x[0]='\0';
    y[0]='\0';
    cin.getline(c,100);
    p=strtok(c," ");
    while(p!=NULL)
    {
        if(strlen(p) >= n)
        {
            strcat(x,p);
            strcat(x," ");
        }
        else{
            strcat(y,p);
            strcat(y," ");
        }
        p=strtok(NULL," ");
    }
    if(strlen(x)==0 || strlen(y)==0)
        fout<<"nu exista";
    else{
        for(int i=0;i<strlen(x);i++)
        {
            while(x[i]!=' ')
            {   
                fout<<x[i];
                i++;
            }   
            fout<<'\n';
        }
        for(int i=0;i<strlen(y);i++)
        {
            while(y[i]!=' ')
            {   
                fout<<y[i];
                i++;
            }   
            fout<<'\n';
        }
    }
}

void model2020_s3_3()
{
    unsigned long long n,x,y,rez=0;
    fin>>n;
    fin>>y;
    rez=n-y;
    while(fin>>x)
    {
        if(x!=y)
            rez=rez+(y-x-1);
        y=x;
    }
    fout<<rez+(y-1);
    fin.close();
}

void fii(long n)
{
    
    int i,j;
    for(i=1;i<=sqrt(n);i++)
    {
        j=n/i;
        if(j*i==n)
            cout<<"("<<j<<" "<<i<<")"<<" ";
    }
}

void test_antrenament_6_s3_3()
{
    int p1,p2,a,b,c,d,i;
    cin>>p1>>p2;
    int nr = 0;
    for(a=1;a<=p1;a++)
    {
        b=p1/a;
        if(a<=9 && b<=9 && a*b==p1)
        {
            for(c=1;c<=p2;c++)
            {
                d=p2/c;
                if(c<=9&&d<=9&&c*d==p2)
                {
                    for(i=0;i<=9;i++)
                    {
                        nr++;
                        fout<<a<<b<<i<<i<<i<<c<<d<<" ";
                    }       
                }
            }
        }
    }
    cout<<nr;
}

void varianta2_teste_antrenament_s3_2()
{
    char c[101],*p;
    cin.getline(c,100);
    p=strchr(c,'-');
    while(p!=NULL)
    {
        int x = strchr(p,' ')-p;
        strcpy(p,p+x);
        p=strchr(p+1,'-');
    }
    cout<<c;
}

struct cerc{
    float raza;
    struct punct{
        float x,y;
    }centru;
}fig;



void varianta3_teste_antrenament_s3_3()
{
    long x,cnt=0,p1n,p2n;
    p1n=p2n=0;
    while(fin>>x)
    {
        cnt++;
        if(x<0)
        {
            if(p1n==0)
                p1n=cnt;
            else p2n=cnt;
        }
    }
    if(cnt-p1n+1>p2n)
        cout<<cnt-p1n+1;
    else cout<<p2n;
    fin.close();
}

void generatoare(long n)
{
    long a,b;
    int ok=0;
    for(a=2;a<=n;a+=2)
    {
        for(b=1;b<=n;b++)
            if((a*b+a/b) == n)
            {
                cout<<a<<"-"<<b<<" ";
                ok=1;
            }
    }
    if(ok==0)
        cout<<"nu exista";
}

void varianta4_teste_antrenament_s3_3()
{
    long x,y,contor=1,ok=0;
    fin>>y;
    while(fin>>y)
    {
        if(x==y)
            contor++;
        else{
            if(contor==2)
            {
                fout<<x<<" ";
                ok=1;
            }
            contor=1;
        }
        x=y;
    }
    if(contor==2)
        fout<<x,ok=1;
    if(!ok)
        fout<<"NU EXISTA";
    
}

void varianta3_teste_antrenament_s2_3()
{
    int n,a[21][21],i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            a[i][j] = abs(n-i-j+1);
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<'\n';
    }
}

int baza(unsigned long n)
{
    int base = 0;
    do{
        if(base < n%10)
            base = n%10;
        n=n/10;
    }while(n!=0);
    return base+1;
}

void varianta5_teste_antrenament_s3_2()
{
    char c[101],*p;
    cin.getline(c,100);
    p=strtok(c," ");
    int counter=0,i;
    while(p!=NULL)
    {
        if(strchr(p,',')==0)
        {
            int nr = 0;
            for(i=0;i<strlen(p);i++)
            {
                if(strchr("0123456789",p[i])!=0)
                    nr++;
            }
            if(nr==strlen(p))
                counter++;
        }
        p=strtok(NULL," ");
    }
    cout<<counter;
}

//Kadane
void varianta5_teste_antrenament_s3_3()
{
    long sum,max_sum=0;
    int x;
    fin>>x;
    sum=max_sum=x;
    if(sum<0)
        sum=0;
    while(fin>>x)
    {
        sum=sum+x;
        if(sum>max_sum)
            max_sum = sum;
        if(sum<0)
            sum=0;
    }
    cout<<max_sum;
    fin.close();
}

void varianta9_teste_antrenament_s3_2()
{
    char cuv[21][21],*p;
    short n,i;
    fin>>n;
    fin.get();
    for(i=1;i<=n;i++)
    {
        fin>>cuv[i];
        fin.get();
    }
    for(i=1;i<n;i++)
    {
        p=strstr(cuv[i],cuv[n]);
        if(strcmp(cuv[i],p) == 0)
        {
            cout<<cuv[i]<<" ";
        }
    }
}

void varianta9_teste_antrenament_s3_3()
{
    long x,k;
    fin>>k;
    long max_value = -1,counter_max=0,total=0;
    while(fin>>x)
    {
        if(x%k==0)
        {
            counter_max++;
        }
        else{
            if(counter_max>max_value)
            {
                max_value=counter_max;
                total=1;
            }
            else if(counter_max == max_value)
            {
                total++;
            }
            counter_max = 0;
        }
    }
    if(counter_max>max_value)
    {
        max_value=counter_max;
        total=1;
    }
    else if(counter_max == max_value)
    {
        total++;
    }
    cout<<max_value<<" "<<total;
    fin.close();
}

void varianta10_teste_antrenament_s3_2()
{
    char sir[256],aux[256];
    char *p,*x;
    fin.getline(sir,100);
    p=sir;
    x=strchr(sir,' ');
    int a,b;
    a=b=-1;
    aux[0]='\0';
    while(x!=NULL)
    {
        x=x+1;
        if(strchr(p,' ')!=NULL)
        {
            a=strchr(p,' ')-p;
            a--;
        }
        if(strchr(x,' ')!=NULL)
        {
            b=strchr(x,' ')-x;
            b--;
        }

        if(p[a] == x[b] && (a!=-1 && b!=-1))
        {
            strncat(aux,p,a+1);
            strcat(aux," succes ");
        }
        else{
            strncat(aux,p,a+1);
            strcat(aux," ");
        }
        p=x;
        x=strchr(x+1,' ');
        a=b=-1;
    }
    strcat(aux,p);
    strcpy(sir,aux);
    fout<<sir;
}

void prodprim(long n,long &p)
{
    long d=2,x;
    p=1;
    while(n<=d)
    {
        x=1;
        while(n%d==0)
        {
            n=n/d;
            x=d;
        }
        p=p*x;
        d=d+1;
    }
}

void varianta6_teste_antrenament_s3_2()
{
    char c[101],*p;
    int nr = 0;
    cin.getline(c,100);
    p=strtok(c," ");
    while(p!=NULL)
    {
        nr=0;
        for(int i=0;i<strlen(p);i++)
        {
            if(strchr("aeiou",p[i])!=0)
                nr++;
        }
        if(nr<strlen(p)-nr)
            cout<<p<<'\n';
        p=strtok(NULL," ");
    }
}



int main()
{
   // varianta6_teste_antrenament_s3_3();
	return 0;
}