#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; typedef long long ll; const int INF = 1<<30; const ll INFLL = 1LL<<60; //const ll MOD = 998244353; const double INFD = 1.0E10; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, -1, 0, 1}; //const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1}; //const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; using Pair = pair; using Graph = vector>; using mint = atcoder::modint998244353; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); ll n, k, q; cin >> n >> k >> q; vector a(n); for (int i = 0; i < n; i++) cin >> a[i]; priority_queue pq1; //小さいいグループ priority_queue, greater> pq2; //大きいグループ pq2.push(INFLL); sort(a.begin(), a.end()); for (int i = 0; i < n; i++){ if (i < k) pq1.push(a[i]); else pq2.push(a[i]); } while (q--){ int t; cin >> t; if (t == 1){ ll x; cin >> x; pq2.push(x); ll v = pq1.top(); ll u = pq2.top(); if (v > u){ pq1.pop(); pq1.push(u); pq2.pop(); pq2.push(v); } } if (t == 2){ ll y; cin >> y; ll v = pq1.top(); ll u = pq2.top(); if (v + y > u){ pq1.pop(); pq1.push(u); pq2.pop(); pq2.push(v + y); } else{ pq1.pop(); pq1.push(v + y); } } if (t == 3){ cout << pq1.top() << '\n'; } } return 0; }