#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int N, Q;
	cin >> N >> Q;
	multiset<ll> A;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		A.insert(a);
	}
	// A[i]
	auto Ai = [&](int i) { auto d = A.begin(); advance(d, i); return *d; };
	multiset<ll> B, C;
	set<int> S;
	map<int, ll> d;
	while (Q--) {
		int t; cin >> t;
		if (t == 1) {
			int k; ll x; cin >> k >> x;
			k--;
			if (S.find(k) != S.end()) {
				B.erase(B.find(Ai(k)));
				C.erase(C.find(d[k]));
			}
			B.insert(Ai(k));
			C.insert(x);
			d[k] = x;
			S.insert(k);
		}
		if (t == 2) {
			for (ll i: B) {
				A.erase(A.find(i));
			}
			B.clear();
			for (ll i: C) {
				A.insert(i);
			}
			C.clear();
		}
		if (t == 3) {
			int k; cin >> k;
			k--;
			ll le = 1, ri = 1e18 + 1;
			while (le + 1 < ri) {
				ll mi = (le + ri) / 2;
				int c = distance(A.begin(), A.upper_bound(mi)) - distance(B.begin(), B.upper_bound(mi)) + distance(C.begin(), C.upper_bound(mi));
				if (c > k) {
					ri = mi;
				} else {
					le = mi;
				}
			}
			cout << ri << '\n';
		}
	}
}