#include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for(i = 0; i < n; i++) #define int long long using namespace std; using namespace atcoder; int n, K, q; int a[100000]; priority_queue que1; priority_queue, greater> que2; signed main() { int i; cin >> n >> K >> q; rep(i, n) cin >> a[i]; rep(i, n) { que1.push(a[i]); if (que1.size() > K) { que2.push(que1.top()); que1.pop(); } } rep(i, q) { int t; cin >> t; if (t == 1) { int x; cin >> x; que1.push(x); if (que1.size() > K) { que2.push(que1.top()); que1.pop(); } } if (t == 2) { int y; cin >> y; int x = que1.top(); que1.pop(); if (!que2.empty() && que2.top() < x + y) { que1.push(que2.top()); que2.pop(); que2.push(x + y); } else { que1.push(x + y); } } if (t == 3) { cout << que1.top() << endl; } } return 0; }