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

#ifndef ONLINE_JUDGE
#include "algo/debug.h"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


class MergeSortTree {
public:
	MergeSortTree(const vector<int>& data) : n(data.size()) {
		arr = data;
		tree.resize(4 * n);
		build(1, 0, n - 1);
	}

	void update(int idx, int value) {
		arr[idx] = value;
		update(1, 0, n - 1, idx);
	}

	void sortArray() {
		sort(arr.begin(), arr.end());
		build(1, 0, n - 1); // rebuild the tree
	}

	int query(int idx) {
		return arr[idx];
	}

private:
	vector<int> arr;
	vector<vector<int>> tree;
	int n;

	void build(int node, int start, int end) {
		if (start == end) {
			tree[node] = {arr[start]};
		} else {
			int mid = (start + end) / 2;
			build(2 * node, start, mid);
			build(2 * node + 1, mid + 1, end);
			merge(tree[2 * node].begin(), tree[2 * node].end(),
			      tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
			      back_inserter(tree[node]));
		}
	}

	void update(int node, int start, int end, int idx) {
		if (start == end) {
			tree[node] = {arr[start]};
		} else {
			int mid = (start + end) / 2;
			if (start <= idx && idx <= mid) {
				update(2 * node, start, mid, idx);
			} else {
				update(2 * node + 1, mid + 1, end, idx);
			}
			tree[node].clear();
			merge(tree[2 * node].begin(), tree[2 * node].end(),
			      tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
			      back_inserter(tree[node]));
		}
	}
};


void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	MergeSortTree mst(a);

	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int k, x;
			cin >> k >> x;
			k--;
			mst.update(k, x);
		} else if (type == 2) {
			mst.sortArray();
		} else if (type == 3) {
			int k;
			cin >> k;
			k--;
			cout << mst.query(k) << endl;
		}
	}
}

signed main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
#endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int t = 1;
	//cin >> t;

	while (t--) {
		solve();
	}

	// cerr << "Time elapsed: " << ((long double)clock() / CLOCKS_PER_SEC) << " s.\n";
}