#include <iostream>

using namespace std;
int a[65536]; ///2^16;
int os[65536];
int N,M;
int cs[50001],h[50001]; ///csucsok, hosszak
int mhat,maxh=0;
void frissit(int cs, int valt)
{
    a[cs]+=valt;
    if(2*cs<mhat)
    {   frissit(2*cs,valt); frissit(2*cs+1,valt); }
}
int maxmag()
{
    int k=mhat/2;
    int maxi=a[k];
    for(int i=k+1;i<mhat;i++) if(a[i]>maxi)maxi=a[i];
    return maxi;
}
void kiir()
{
    for(int i=1;i<mhat;i++) cout<<a[i]<<" ";
    cout<<endl;
}
int szint(int x)
{
    int db=0;
    while(x>1)
    {
        db++;x/=2;
    }
    return db;
}
void keres(int x, int & k, int & v) ///kezdoertek a levelek szintjen
{
    v=x+1;
    while(x<mhat/2)
    {
        x*=2;v=v*2;
    }
    k=x;
    v--;
}
void frissit2(int k, int v, int valt, int &maxi)
{
    maxi=a[k];a[k]+=valt;
    for(int i=k+1;i<=v;i++)
    {
        a[i]+=valt;
        maxi=max(a[i],maxi);
    }

}
void be()
{
    ///inicializal a
    cin>>N>>M;
    mhat=(1<<N);
    a[1]=0;os[1]=0;
    for(int i=2;i<mhat;i++)
       {
         a[i]=a[i/2]+1;os[i]=1;
       }
    //kiir();
    for(int i=1;i<=M;i++)
    {
        cin>>cs[i]>>h[i];
    }
    int k,v;
    int valtozas;
    maxh=maxmag();
    int maxh_eddig=maxh;
    for(int i=1;i<=M;i++)
    {
        valtozas=h[i]-os[cs[i]];
        if(valtozas!=0)
        {
            os[cs[i]]=h[i];
            keres(cs[i],k,v);
            //frissit(cs[i],valtozas);

            frissit2(k,v,valtozas,maxh);
            //cout<<maxmag()<<"\n";
            if(maxh>maxh_eddig) maxh_eddig=maxh;
            else maxh_eddig=maxmag();
        }
        cout<<maxh_eddig<<"\n";
         // kiir();cout<<k<<v<<valtozas;
    }
}

int main()
{
    be();

    return 0;
}