#include <iostream>
#include <fstream>

using namespace std;

int gyorshatvany(int n)
{
    if (n==0)
        return 1;
    else
    {
        int hatvany=gyorshatvany(n/2); // 2^n/2
        if (n%2==0)
        {
            return hatvany * hatvany;
        }
        else
            return hatvany * hatvany * 2;
    }
}

void alakit(int suly[], int hossz[], int csp , int darabcsucs)
{
    hossz[csp]=hossz[csp/2]+suly[csp];
    if (csp*2 < darabcsucs){
        alakit(suly,hossz,csp*2, darabcsucs);
        alakit (suly, hossz, csp*2+1, darabcsucs);
    }
}
int main()
{

    int n,m;
    //ifstream fin("be.in");
    cin>>n>>m;
    int darabcsucs=gyorshatvany(n);
    int suly[darabcsucs]={0},hossz[darabcsucs]={0};
    int x,y;
    for (int i=2;i<darabcsucs;i++)
    {
        suly[i]=1;
        hossz[i]=hossz[i/2]+1;
    }
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y;
        suly[x]=y;
        alakit(suly,hossz,x,darabcsucs);
        int maxi=-1;
        for (int i=darabcsucs-1;i>=darabcsucs/2;i--)
        {
            if (hossz[i]>maxi)
                maxi=hossz[i];
        }
        cout<<maxi<< endl;
    }
    return 0;
}