//建立两个堆，一个大根堆，一个小根堆。从K处劈开
#include <bits/stdc++.h>


using namespace std;
int n, m, k;
const int maxn = 2e5+10;
int a[maxn];


int main() {
    priority_queue<int, vector<int>, less<int> >z;
    priority_queue<int, vector<int>, greater<int> >y;
    int val;
    cin>>n>>m>>k;
    //建立左右根堆
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1, a+n+1);
    for (int i=1;i<=n;i++) {
        if (i<=k) {
//             cout<<i<<endl;
            z.push(a[i]);
        } else {
            y.push(a[i]);
        }
    }
    int op;
//     cout<<z.top()<<endl;
    //开始操作
    while (m--) {
        cin>>op;
        if (op==1) {
            cin>>val;
            if (z.size()<k) z.push(val);
            else if (val>=z.top()) {
                y.push(val);
            } else {
                y.push(z.top());
                z.pop();
                z.push(val);
            }
        }
        if (op==2) {
            if (z.size()<k) {
                cout<<-1<<endl;
            } else
            cout<<z.top()<<endl;
        }
    }
    
    return 0;
}