#include <bits/stdc++.h>
#define For(i, a, b) for(long long i = a; i < b; i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(long long i = a; i >= b; i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
using namespace std;

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

template <class S, class T = int>
struct IntervalSet {
    public:
    struct Node {
        S l, r;
        T val;
        
        bool operator<(const Node &a) const {
            return (l != a.l ? l < a.l : r < a.r);
        }
    };
    
    IntervalSet() {
        s.insert({-SINF, -SINF, 0});
        s.insert({SINF, SINF, 0});
    }
    
    bool covered(S l, S r) {
        assert(l <= r);
        if (l == r) {
            return true;
        }
        auto it = prev(s.upper_bound({l, SINF, 0}));
        return (it->l <= l && r <= it->r);
    }
    
    bool covered(S x) {
        return covered(x, x + 1);
    }
    
    // [l, r) を含む区間 なければ [l, r) のすぐ左の区間
    auto get(S l, S r) {
        assert(l < r);
        return prev(s.upper_bound({l, SINF, 0}));
    }
    
    auto get(S x) {
        return get(x, x + 1);
    }
    
    template <class ADD, class DEL>
    void insert(S l, S r, T x, ADD add, DEL del) {
        assert(l <= r);
        if (l == r) {
            return;
        }
        auto it = prev(s.upper_bound({l, SINF, 0}));
        if (it->l <= l && r <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            if (x == X) {
                return;
            }
            del(L, R, X);
            s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
            if (r < R) {
                add(r, R, X);
                s.insert({r, R, X});
            }
            add(l, r, x);
            s.insert({l, r, x});
            return;
        }
        if (it->l <= l && l <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            it = s.erase(it);
            if (x == X) {
                l = L;
            } else {
                if (L < l) {
                    add(L, l, X);
                    s.insert({L, l, X});
                }
            }
        } else {
            it = next(it);
        }
        while (it->r <= r) {
            del(it->l, it->r, it->val);
            it = s.erase(it);
        }
        if (it->l <= r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            if (x == X) {
                r = R;
            } else {
                if (r < R) {
                    add(r, R, X);
                    s.insert({r, R, X});
                }
            }
        }
        add(l, r, x);
        s.insert({l, r, x});
        return;
    }
    
    template <class ADD, class DEL>
    void insert(S l, S r, ADD add, DEL del) {
        insert(l, r, T(0), add, del);
    }
    
    void insert(S l, S r, T x = 0) {
        auto func = [](S l, S r, T x) {};
        insert(l, r, x, func, func);
    }
    
    void insert(S l) {
        auto func = [](S l, S r, T x) {};
        insert(l, l + 1, T(0), func, func);
    }
    
    template <class ADD, class DEL>
    void erase(S l, S r, ADD add, DEL del) {
        assert(l <= r);
        if (l == r) {
            return;
        }
        auto it = prev(s.upper_bound({l, SINF, 0}));
        if (it->l <= l && r <= it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
            if (r < R) {
                add(r, R, X);
                s.insert({r, R, X});
            }
            return;
        }
        if (it->l <= l && l < it->r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            it = s.erase(it);
            if (L < l) {
                add(L, l, X);
                s.insert({L, l, X});
            }
        } else {
            it = next(it);
        }
        while (it->r <= r) {
            del(it->l, it->r, it->val);
            it = s.erase(it);
        }
        if (it->l < r) {
            S L = it->l, R = it->r;
            T X = it->val;
            del(L, R, X);
            s.erase(it);
            add(r, R, X);
            s.insert({r, R, X});
        }
        return;
    }
    
    void erase(S l, S r) {
        auto func = [](S l, S r, T x) {};
        erase(l, r, func, func);
    }
    
    void erase(S l) {
        auto func = [](S l, S r, T x) {};
        erase(l, l + 1, func, func);
    }
    
    int size() {
        return (int)s.size() - 2;
    }
    
    S mex(S x = 0) {
        auto it = prev(s.upper_bound({x, SINF, 0}));
        if (it->l <= x && x < it->r) {
            return it->r;
        } else {
            return x;
        }
    }
    
    set<Node> get_all() {
        return s;
    }
    
    void dump() {
        for (auto node : s) {
            if (abs(node.l) != SINF) {
                cout << "[" << node.l << ", " << node.r << "):" << node.val << " ";
            }
        }
        cout << endl;
    }
    
    private:
    set<Node> s;
    S SINF = numeric_limits<S>::max();
    T TINF = numeric_limits<T>::max();
};

int main() {
    lint d;
    int q;
    cin >> d >> q;
    IntervalSet<lint> s;
    lint ans = 0;
    while (q--) {
        lint a, b;
        cin >> a >> b;
        b++;
        s.insert(a, b);
        auto it = s.get(a, b);
        ans = max(ans, it->r - it->l);
        cout << ans << endl;
    }
}