#include using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using i128 = __int128_t; using uc = unsigned char; #define Max(X,Y) (((X) > (Y)) ? (X) : (Y)) #define Min(X,Y) (((X) < (Y)) ? (X) : (Y)) #define yes cout << "Yes" << endl; #define no cout << "No" << endl; #define YES yes return 0; #define NO no return 0; #define pc cout << count << endl; #define PC pc return 0; #define INF 0x1fffffff #define Eps LDBL_EPSILON #ifdef DEBUG #define dbg(X) cerr << X << endl #else #define dbg(...) #endif template inline ostream& operator<<(ostream& os, const vector& v) noexcept { if(!v.empty()) os << v[0]; for(size_t i = 1; i < v.size(); i++) os << " " << v[i]; return os; } template void swap(T& a, T& b) { auto x = a; a = b; b = x; } template size_t partition(vector& list, size_t start, size_t end) { auto pivot = list[end-1]; auto hi = start; for(auto i = start; i < end - 1; i++) { if(list[i] <= pivot) { swap(list[hi], list[i]); hi++; } } swap(list[hi], list[end-1]); return hi; } template void quicksort(vector& list, size_t l, size_t r) { if(l < r) { auto pivot = partition(list, l, r); quicksort(list, l, pivot); quicksort(list, pivot + 1, r); } } struct string_set { map> registry = {}; bool contains(string_view s) { auto h = hash()(s); return registry.contains(h) && find(registry[h].begin(), registry[h].end(), s) != registry[h].end(); } void add(string_view s) { auto h = hash()(s); auto pos = find(registry[h].begin(), registry[h].end(), s); if(pos != registry[h].end()) return; registry[h].push_back(s); } void remove(string_view s) { auto h = hash()(s); if(!registry.contains(h)) return; auto pos = find(registry[h].begin(), registry[h].end(), s); if(pos == registry[h].end()) return; registry[h].erase(pos); } }; template struct BIT { ll n; vector tree; BIT(ll size) : n(size + 1), tree(n, 0) {} void add(ll i, T x) { for (ll idx = i; idx < n; idx += (idx & -idx)) { tree[idx] += x; } } T sum(ll i) { T s(0); for (ll idx = i; idx > 0; idx -= (idx & -idx)) { s += tree[idx]; } return s; } }; struct RSQ { ll N; vector tree; RSQ(ll max) : N(), tree(max*4, 0) { ll x = 1; while(max > x) x*=2; N = x; } void inc(ll i) { i += N - 1; tree[i]++; while (i > 0) { i = (i - 1) / 2; tree[i]++; } } ll find(ll k) { auto [cod, num] = find_sect(k, 0); if(cod) return num; return -1; } pair find_sect(ll k, ll n) { if(n >= N-1) { if(tree[n] < k) { return {false, k - tree[n]}; } return {true, n-N-1}; } if(tree[n] < k) return {false, k - tree[n]}; auto [cod, num] = find_sect(k, 2*n+1); if(cod) { return {cod, num}; } return find_sect(k-num, 2*n+2); } }; int main() { cin.tie(nullptr); ll N, K, Q; cin >> N >> K >> Q; vector A; A.reserve(N+Q); for(ll i = 0; i < N; i++) { ll a; cin >> a; A.push_back(a); } sort(A.begin(), A.end()); for(; Q>0; Q--) { int q; cin >> q; if(q == 1) { ll x; cin >> x; A.push_back(x); for(ll i = A.size()-1; i > 0; i--) { if(A[i-1] > x) { A[i] = A[i-1]; A[i-1] = x; } else break; } } else if(q == 2) { ll y; cin >> y; ll pl = A[K-1]+y; for(ll i = K-1; i < A.size()-1; i++) { if(A[i+1] < pl) { A[i] = A[i+1]; A[i+1] = pl; } else break; } } else { cout << A[K-1] << endl; } } }