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

const int Maxn = 1e5+5;

namespace Josh_zmf {
	
	template <int HEAP_NUM, int NODE_NUM, typename T> struct HEAP {
		// private:
			static int node_num;
			static struct Node { 
				int lson, rson, dist; T val; 
				bool operator < (const Node &a) const { return val<a.val; }
			} node[NODE_NUM+5];
			static int new_node(T val) {
				int t = ++node_num;
				node[t] = Node { 0, 0, 0, val };
				return t;
			}
			static int merge(int x, int y) {
				if(!x || !y)	return x|y;
				if(node[x].val < node[y].val)	swap(x, y);
				node[x].rson = merge(node[x].rson, y);
				if(node[node[x].lson].dist < node[node[x].rson].dist)	swap(node[x].lson, node[x].rson);
				node[x].dist = node[node[x].rson].dist+1;
				return x;
			}
		// public:
			struct Heap {
				// private:
				// public:
					int root;
					inline T top() {
						return node[root].val;
					}
					inline void pop() {
						root = merge(node[root].lson, node[root].rson);
					}
					inline void insert(T val) {
						int t = new_node(val);
						root = merge(root, t);
					}
			} heap[HEAP_NUM+5];
			inline void merge(Heap &a, Heap &b) {
				if(a.root == b.root)	return ;
				a.root = b.root = merge(a.root, b.root);
			}
			Heap& operator [] (const int &i) { return heap[i]; }
	};

	struct Value { 
		int id, val; 
		bool operator < (const Value &a) const { return val^a.val ?val<a.val :id<a.id; }
	}; HEAP <Maxn, Maxn, Value> h;
	
	int N, M; bool del[Maxn];

	int main() {
		cin>> N>> M;
		for(int i=1, x; i<=N; i++) {
			cin>> x;
			h[i].insert( Value {x, i} );
		}
		int opt, x, y;
		while(M--) {
			cin>> opt>> x;
			if(opt == 1) {
				cin>> y;
				if(del[x] || del[y])	continue;
				h.merge(h[x], h[y]);
			} else {
				if(del[x])	cout<< "-1\n";
				else	cout<< h[x].top().val<< '\n', del[x]=1, h[x].pop();
			}
		}
		return 0;
	}

}

int main() {
	Josh_zmf::main();
	return 0;
}