#include using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k, q; cin >> n >> k >> q; priority_queue pq; priority_queue, greater> pq2; pq2.emplace(1ll << 60); int v; for(int i = 0; i < n; i++){ cin >> v; pq.emplace(v); } auto update = [&](){ while(pq.size() > k){ int v = pq.top(); pq.pop(); pq2.emplace(v); } while(pq.top() > pq2.top()){ int v = pq.top(); pq.pop(); int v2 = pq2.top(); pq2.pop(); pq.emplace(v2); pq2.emplace(v); } }; update(); while(q--){ int cmd; cin >> cmd; if(cmd == 1){ int x; cin >> x; pq.emplace(x); update(); }else if(cmd == 2){ int y; cin >> y; ll v = pq.top(); pq.pop(); pq.emplace(v + y); update(); }else{ cout << pq.top() << '\n'; } } }