#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 LINF 0x1fffffffffffffff #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); } }; template class binary_trie { struct node { int cnt; node *ch[2]; node() : cnt(0), ch{ nullptr, nullptr } {} }; node* add(node* t, U val, int b = B - 1) { if (!t) t = new node; t->cnt += 1; if (b < 0) return t; bool f = (val >> (U)b) & (U)1; t->ch[f] = add(t->ch[f], val, b - 1); return t; } node* sub(node* t, U val, int b = B - 1) { assert(t); t->cnt -= 1; if (t->cnt == 0) return nullptr; if (b < 0) return t; bool f = (val >> (U)b) & (U)1; t->ch[f] = sub(t->ch[f], val, b - 1); return t; } U get_min(node* t, U val, int b = B - 1) const { assert(t); if (b < 0) return 0; bool f = (val >> (U)b) & (U)1; f ^= !t->ch[f]; return get_min(t->ch[f], val, b - 1) | ((U)f << (U)b); } U get(node* t, int k, int b = B - 1) const { if (b < 0) return 0; int m = t->ch[0] ? t->ch[0]->cnt : 0; return k < m ? get(t->ch[0], k, b - 1) : get(t->ch[1], k - m, b - 1) | ((U)1 << (U)b); } int count_lower(node* t, U val, int b = B - 1) { if (!t || b < 0) return 0; bool f = (val >> (U)b) & (U)1; return (f && t->ch[0] ? t->ch[0]->cnt : 0) + count_lower(t->ch[f], val, b - 1); } node *root; public: binary_trie() : root(nullptr) {} int size() const { return root ? root->cnt : 0; } bool empty() const { return !root; } void insert(U val) { root = add(root, val); } void erase(U val) { root = sub(root, val); } U max_element(U bias = 0) const { return get_min(root, ~bias); } U min_element(U bias = 0) const { return get_min(root, bias); } int lower_bound(U val) { // return id return count_lower(root, val); } int upper_bound(U val) { // return id return count_lower(root, val + 1); } U operator[](int k) const { assert(0 <= k && k < size()); return get(root, k); } int count(U val) const { if (!root) return 0; node *t = root; for (int i = B - 1; i >= 0; i--) { t = t->ch[(val >> (U)i) & (U)1]; if (!t) return 0; } return t->cnt; } }; int main() { cin.tie(nullptr); ll N, K, Q; cin >> N >> K >> Q; binary_trie A; for(ll i = 0; i < N; i++) { ull a; cin >> a; A.insert(a); } for(; Q>0; Q--) { int q; cin >> q; if(q == 1) { ll x; cin >> x; A.insert(x); } else if(q == 2) { ll y; cin >> y; ull pl = A[K-1]; A.erase(pl); A.insert(pl+y); } else { cout << A[K-1] << endl; } } }