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

using ar2 = array<int, 2>;
using i64 = long long;
#define sz(v) int(v.size())

struct T {
    vector<int> t, v;
    void init(int n) {
        t.resize(n, 0);
        v.resize(n, 0);
    }
    void add(int i, int x) {
        v[i] += x;
        while (i < sz(t)) {
            t[i] += x;
            i |= i + 1;
        }
    }
    int sum(int i) {
        int x = 0;
        while (i >= 0) {
            x += t[i];
            i &= i + 1, i--;
        }
        return x;
    }
    int find(int k) {
        int i = 0;
        for (int p = 1 << 18; p; p >>= 1) {
            if (i + p <= sz(t) && t[i + p - 1] < k) {
                i += p;
                k -= t[i - 1];
            }
        }
        return i;
    }
    int next(int i) {
        while (!v[i]) {
            i++;
        }
        return i;
    }
};

struct D {
    i64 a; ar2 b;
    D operator+(const D &o) const {
        return {a + o.a, ar2{b[0] + o.b[0], b[1] + o.b[1]}};
    }
    void app(int t, i64 v) {
        a += v * b[t];
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int size[2];
    T ds[2];
    for (int t = 0; t < 2; t++) {
        size[t] = n;
        ds[t].init(n + 1);
        for (int i = 1; i <= n; i++) {
            ds[t].add(i, 1);
        }
    }
    vector<ar2> x(n);
    vector<array<D, 2>> d(n);
    auto cyc = [&](int i) {
        return x[i][0] == 0 && x[i][1] == 0;
    };
    struct info {
        bool c[2][2];
        pair<ar2, D> t[2][2];
        i64 lz[2];
        info() {
            lz[0] = lz[1] = 0;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    c[i][j] = 0;
                    t[i][j] = {ar2{0, 0}, D{0, ar2{0, 0}}};
                }
            }
        }
    };
    vector<info> tr(n * 4);
    int who = -1;
    auto pul = [&](int k, int l, int r) {
        if (r - l + 1 == 1) {
            return;
        }
        if (r - l + 1 <= 3) {
            for (int j = 0; j < 2; j++) {
                for (int t = 0; t < 2; t++) {
                    ar2 u = {l + j, t};
                    D z{0, ar2{0, 0}};
                    while (u[0] <= r && !cyc(u[0])) {
                        z = z + d[u[0]][u[1]];
                        u[0] += x[u[0]][u[1]];
                        u[1] ^= 1;
                    }
                    if (u[0] <= r) {
                        tr[k].c[j][t] = 1;
                    } else {
                        tr[k].c[j][t] = 0;
                        tr[k].t[j][t] = {ar2{u[0] - r - 1, u[1]}, z};
                    }
                }
            }
        } else {
            for (int j = 0; j < 2; j++) {
                for (int t = 0; t < 2; t++) {
                    if (tr[k * 2].c[j][t]) {
                        tr[k].c[j][t] = 1;
                    } else {
                        auto [j_, t_] = tr[k * 2].t[j][t].first;
                        tr[k].c[j][t] = tr[k * 2 + 1].c[j_][t_];
                        if (!tr[k].c[j][t]) {
                            tr[k].t[j][t].first = tr[k * 2 + 1].t[j_][t_].first;
                            tr[k].t[j][t].second = tr[k * 2].t[j][t].second + tr[k * 2 + 1].t[j_][t_].second;
                        }
                    }
                }
            }
        }
    };
    auto put = [&](int k, int l, int r, int t, i64 v) {
        if (r - l + 1 <= 3) {
            for (int i = l; i <= r; i++) {
                if (i == who) {
                    continue;
                }
                d[i][0].app(t, v);
                d[i][1].app(t, v);
            }
        }
        tr[k].lz[t] += v;
        for (int a = 0; a < 2; a++) {
            for (int b = 0; b < 2; b++) {
                tr[k].t[a][b].second.app(t, v);
            }
        }
    };
    auto pus = [&](int k, int l, int r) {
        for (int t = 0; t < 2; t++) {
            if (tr[k].lz[t]) {
                int m = (l + r) / 2;
                put(k * 2, l, m, t, tr[k].lz[t]);
                put(k * 2 + 1, m + 1, r, t, tr[k].lz[t]);
                tr[k].lz[t] = 0;
            }
        }
    };
    auto bld = [&](auto bld, int k, int l, int r) -> void {
        if (r - l + 1 <= 3) {
            pul(k, l, r);
        } else {
            int m = (l + r) / 2;
            bld(bld, k * 2, l, m);
            bld(bld, k * 2 + 1, m + 1, r);
            pul(k, l, r);
        }
    };
    auto upd = [&](auto upd, int k, int l, int r, int i) -> void {
        if (r - l + 1 <= 3) {
            pul(k, l, r);
        } else {
            int m = (l + r) / 2;
            pus(k, l, r);
            i <= m ? upd(upd, k * 2, l, m, i) : upd(upd, k * 2 + 1, m + 1, r, i);
            pul(k, l, r);
        }
    };
    auto qry = [&](auto qry, int k, int l, int r, ar2 &u) -> i64 {
        assert(u[0] >= l && u[0] <= r);
        if (r - l + 1 <= 3) {
            i64 z = 0;
            while (u[0] <= r && !cyc(u[0])) {
                z += d[u[0]][u[1]].a;
                u[0] += x[u[0]][u[1]];
                u[1] ^= 1;
            }
            if (u[0] <= r) {
                return -1;
            } else {
                return z;
            }
        }
        if (u[0] == l || u[0] == l + 1) {
            if (tr[k].c[u[0] - l][u[1]]) {
                return -1;
            }
            const auto &x = tr[k].t[u[0] - l][u[1]];
            u = ar2{r + 1 + x.first[0], x.first[1]};
            return x.second.a;
        } else {
            int m = (l + r) / 2;
            pus(k, l, r);
            if (u[0] <= m) {
                i64 z = qry(qry, k * 2, l, m, u);
                if (z == -1) {
                    return -1;
                }
                i64 z_ = qry(qry, k * 2 + 1, m + 1, r, u);
                if (z_ == -1) {
                    return -1;
                }
                return z + z_;
            } else {
                return qry(qry, k * 2 + 1, m + 1, r, u);
            }
        }
    };
    auto add = [&](auto add, int k, int l, int r, int ql, int qr, int t, int v) -> void {
        if (r - l + 1 <= 3) {
            for (int i = max(ql, l); i <= min(qr, r); i++) {
                d[i][0].app(t, v);
                d[i][1].app(t, v);
            }
            pul(k, l, r);
            return;
        }
        if (ql <= l && qr >= r) {
            put(k, l, r, t, v);
        } else {
            int m = (l + r) / 2;
            pus(k, l, r);
            if (ql <= m) {
                add(add, k * 2, l, m, ql, qr, t, v);
            }
            if (qr > m) {
                add(add, k * 2 + 1, m + 1, r, ql, qr, t, v);
            }
            pul(k, l, r);
        }
    };
    auto calc = [&](int i, bool u = 0) {
        if (i <= 0 || i >= n) {
            return;
        }
        who = i;
        for (int t = 0; t < 2; t++) {
            int j = ds[t].next(i);
            if (i == j) {
                x[i][t] = ds[t].next(j + 1) - j;
                d[i][t] = D{2 * ds[t].sum(j) + 1, ar2{(t == 0) * 2, (t == 1) * 2}};
            } else {
                x[i][t] = 0;
                d[i][t] = D{2 * ds[t].sum(j) - 1, ar2{(t == 0) * 2, (t == 1) * 2}};
            }
        }
        if (u) {
            upd(upd, 1, 1, n - 1, i);
        }
        who = -1;
    };
    for (int i = 1; i < n; i++) {
        calc(i);
    }
    bld(bld, 1, 1, n - 1);
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            if (x >= n) {
                cout << size[1] + 1 << '\n';
            } else {
                ar2 u{x, 1};
                i64 z = qry(qry, 1, 1, n - 1, u);
                if (z == -1) {
                    cout << "-1\n";
                } else {
                    assert(u[0] == n);
                    z += size[u[1]];
                    cout << z + 1 << '\n';
                }
            }
        } else if (t == 2) {
            assert(x != size[0]);
            if (x <= size[0]) {
                t = 0;
                x = size[0] - x;
            } else {
                x -= size[0];
                assert(x != size[1]);
                t = 1;
            }
            int p = ds[t].find(x);
            assert(p >= 1);
            ds[t].add(p, -1);
            add(add, 1, 1, n - 1, p, n - 1, t, -1);
            size[t]--;
            calc(p, 1);
            calc(p - 1, 1);
        } else {
            if (x <= size[0]) {
                t = 0;
                x = size[0] - x + 1;
            } else {
                x -= size[0];
                t = 1;
            }
            int p = ds[t].find(x);
            assert(p >= 2);
            ds[t].add(p - 1, 1);
            add(add, 1, 1, n - 1, p - 1, n - 1, t, 1);
            size[t]++;
            calc(p - 1, 1);
            calc(p - 2, 1);
        }
    }
}