from sys import stdin,stdout

def main():
    N,M = [int(i) for i in stdin.readline().split()]
    k = [2**i for i in range(N+1)]
    f = [0,0]+[1]*k[N]
    h = [0]*k[N-1] + [N-1]*k[N-1]
    hdb = {N-1:k[N-1]}
    u = k[N-1]
    s = [0]
    for i in range(1,N+1):
        s = s + [i]*k[i-1]
##    print(s)

    maxi = N-1
    for i in range(M):
        a,uj = [int(i) for i in stdin.readline().split()]
        b = uj-f[a]
        f[a] = uj
        le = N-s[a]
        maxiuj = N-1
        for i in range(a*k[le],a*k[le]+k[le]):
##            print(hdb)
            hdb[h[i]] -= 1
            if hdb[h[i]] == 0:
                del hdb[h[i]]
            h[i] += b
            if h[i] in hdb:
                hdb[h[i]] += 1
            else:
##                print(h[i],hdb)
                hdb[h[i]] = 1
            if h[i] > maxiuj:
                maxiuj = h[i]
        if maxiuj > maxi:
            maxi = maxiuj
        else:
            maxi = max(hdb)
        stdout.write(str(maxi)+'\n')
main()