#include using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) using ll = long long; using ull = unsigned long long; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, k, q; cin >> n >> k >> q; vector a(n); rep(i, n) cin >> a[i]; multiset lt, gt; rep(i, n) { if (lt.size() < k) { lt.insert(a[i]); } else { assert(lt.size() == k); ll x = *lt.rbegin(); if (x <= a[i]) { gt.insert(a[i]); } else { lt.erase(prev(lt.end())); lt.insert(a[i]); gt.insert(x); } } } while (q--) { // cerr << format("{} {}\n", lt, gt); int t; cin >> t; assert(lt.size() == k); if (t == 1) { ll x; cin >> x; ll y = *lt.rbegin(); if (y <= x) { gt.insert(x); } else { lt.erase(prev(lt.end())); lt.insert(x); gt.insert(y); } } if (t == 2) { ll x; cin >> x; ll y = *lt.rbegin(); lt.erase(prev(lt.end())); y += x; ll z = gt.empty() ? 1e18 : *gt.begin(); if (y <= z) { lt.insert(y); } else { gt.erase(gt.begin()); lt.insert(z); gt.insert(y); } } if (t == 3) { cout << *lt.rbegin() << '\n'; } } return 0; }