//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")


// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse,-fgcse-lm")
// #pragma GCC optimize("-ftree-pre,-ftree-vrp")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define sz(x) (int)x.size();
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend();
#define nl '\n'

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const ll inf = 2e9;

ll q;
multiset <ll> s;

ll sec(ll x, ll k){
    auto it = s.upper_bound(x);
    for(int i = 1; i <= k; i++){
        if(it == s.begin())
            return -1;
        it--;
    }
    return *it;
}

ll thir(ll x, ll k){
    auto it = s.lower_bound(x);
    it--;
    for(int i = 1; i <= k; i++){
        it++;
        if(it == s.end())
            return -1;
    }
    return *it;
}

void solve(){
    cin >> q;
    while(q--){
        ll tp, x, k;
        cin >> tp;
        if(tp == 1){
            cin >> x;
            s.insert(x);
        }
        else if(tp == 2){
            cin >> x >> k;
            cout << sec(x, k) << nl;
        }
        else{
            cin >> x >> k;
            cout << thir(x, k) << nl;
        }
    }
}

signed main(){
    speed;
    int T = 1;
    while(T--)
        solve();
}