#include<bits/stdc++.h>
using namespace std;

const int N = 70000;
vector<int> h(N, 1);
vector<int> maxi(N, 1);

int n;

void build(int v, int f){
    if(f>n) return;
    maxi[v] = n-f;
    build(2*v, f+1);
    build(2*v+1, f+1);
}

int main(){
    cin >> n;
    int m; cin >> m;
    build(1, 1);
    while(m--){
        int a, b; cin >> a >> b;
        h[a] = b;
        int x = a/2;
        while(x>=1){
            maxi[x] = max(maxi[2*x] + h[2*x], maxi[2*x+1] + h[2*x+1]);
            x/=2;
        }
        cout << maxi[1] << endl;
    }
}