from sys import stdin,stdout

def main():
    N,M = [int(i) for i in stdin.readline().split()]
    a = [N]   # alatta levő "mélység"
    k = 1
    for i in range(1,N+1):
        a = a + [N-i]*k
        k *= 2
    h = [1]*k

    for i in range(M):
        cs,x = [int(i) for i in stdin.readline().split()]
        h[cs] = x
        while cs > 1:
            c = cs//2
            c2 = c*2
            a[c] = max(h[c2]+a[c2], h[c2+1]+a[c2+1])
            cs = c
        print(a[1])

main()