2782

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

struct Node
{
    Node* l;
    Node* r;
    int key;
    int prior;
    Node(int key, int prior) : key(key), prior(prior), l(nullptr), r(nullptr) {}
};

Node* root = nullptr;

Node* merge(Node* t1, Node* t2) {
    if (t2 == nullptr) return t1;
    if (t1 == nullptr) return t2;
    if (t1->prior > t2->prior) {
        t1->r = merge(t1->r, t2);
        return t1;
    }
    else {
        t2->l = merge(t1, t2->l);
        return t2;
    }
}

pair<Node*, Node*> split(Node* t, int val) {
    if (t == nullptr) return make_pair(nullptr, nullptr);
    if (val > t->key) {
        auto newT = split(t->r, val);
        t->r = newT.first;
        return make_pair(t, newT.second);
    }
    else {
        auto newT = split(t->l, val);
        t->l = newT.second;
        return make_pair(newT.first, t);
    }
}

int GetMin(Node* t) {
    if (t == nullptr) return -1;
    if (t->l == nullptr) return t->key;
    return GetMin(t->l);
}

void insert(Node* cur, int val) {
    auto p = split(root, val);
    if (GetMin(p.second) != val)
        root = merge(merge(p.first, new Node(val, ((rand() << 16) | rand()))), p.second);
    else root = merge(p.first, p.second);
}

int next(int val) {
    auto p = split(root, val);
    int a = GetMin(p.second);
    root = merge(p.first, p.second);
    return a;
}

int main() {
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    srand(time(NULL));

    int n; bool f = 0; int prev = 0;
    fin >> n;
    for (int i = 0; i < n; i++) {
        char ch; int a; fin >> ch >> a;
        if (ch == '+') {
            insert(root, (a + prev * f) % (int)1e9);
            f = 0;
        }
        else {
            f = 1;
            prev = next(a);
            fout << prev << endl;
        }
    }

    fin.close();
    fout.close();
    return 0;
}