Вхідний тест відповідає умові

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    multiset<long long> st;
    long long m, n, y = 0;
    string o;
    bool qm;
    cin >> m;
    while (m--) {
        cin >> o >> n;
        if (o == "+") {
            if (!qm) {
                st.insert(n);
            }
            else{
                st.insert((n + y) % 1000000000);
                qm = false;
            }
        }
        else if (o == "?") {
            qm = true;
            auto it = st.lower_bound(n);
            if (it != st.end()) {
                y = *it;
                cout<<y<<endl;
            }
            else {
                y = -1;
                cout<<y<<endl;
            }
        }
    }
    return 0;
}

C++ solution using multiset