#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>

using namespace std;

#define ls first
#define rs second
#define N int(3e5 + 5)
#define pair pair<int, int>
#define MOD int(1e9)

struct treap {
    int x, y, l, r;

    treap() {}

    treap(int a, int b, int c, int d) {
        x = a, y = b, l = c, r = d;
        //fprintf(stderr, "(%d, %d, %d, %d)\n", a, b, c, d);
    }
};

treap t[N];
int num = 1, root = 1;

int merge(int l, int r) {
    //cerr << l << " " << r << " " << (t[l].r) << " " << t[r].r << endl;
    if (l == 0 || r == 0) return max(l, r);
    if (t[l].y < t[r].y) {
        //cerr << "1 ->\n";
        t[r].l = merge(l, t[r].l);
        return r;
    }
    else {
        //cerr << "2 ->\n";
        t[l].r = merge(t[l].r, r);
        return l;
    }
}

pair split(int v, int x) {
    if (!v) return make_pair(0, 0);
    if (t[v].x < x) {
        pair res = split(t[v].r, x);
        t[v].r = res.ls;
        return make_pair(v, res.rs);
    }
    else {
        pair res = split(t[v].l, x);
        t[v].l = res.rs;
        return make_pair(res.ls, v);
    }
}

int find(int v, int val) {
    if (t[v].x == val) return val;
    if (t[v].x < val) {
        if (!t[v].r) return t[v].x;
        return find(t[v].r, val);
    }
    else {
        if (!t[v].l) return t[v].x;
        return find(t[v].l, val);
    }
}

void print(int v, int sp) {
    if (!v) return;
    print(t[v].r, sp + 1);
    fprintf(stderr, "%*d\n", sp * 5, t[v].x);
    print(t[v].l, sp + 1);
    if (!sp)
        fprintf(stderr, "-------------\n");
}

void insert(int x) {
    if (find(root, x) == x) return;
    int y = rand() * RAND_MAX + rand();
    pair res = split(root, x);
    t[++num] = treap(x, y, 0, 0);
    root = merge(res.ls, num);
    root = merge(root, res.rs);
}

int main() {
    freopen("next.in", "r", stdin);
    freopen("next.out", "w", stdout);

    srand(time(NULL));

    t[1] = treap(-1, rand() * RAND_MAX + rand(), 0, 0);

    int n, prev = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char op;
        int num;
        cin >> op >> num;

        if (op == '?') {
            //print(root, 0);
            pair res = split(root, num);
            int now = res.rs, ans;

            if (!now) {
                ans = -1;
            }
            else {
                while (t[now].l)
                    now = t[now].l;
                ans = t[now].x;
            }
            prev = ans;
            cout << ans << endl;

            root = merge(res.ls, res.rs);
        }
        else {
            insert((num + prev) % MOD);
            prev = 0;
        }
    }

    return 0;
}