#include <algorithm>
// #include <array>
// #include <bitset>
// #include <cassert>
// #include <cctype>
// #include <climits>
// #include <cmath>
// #include <cstdarg>
#include <cstdint>
// #include <cstdio>
// #include <cstdlib>
// #include <cstring>
// #include <ctime>
// #include <deque>
#include <fstream>
// #include <functional>
// #include <iomanip>
#include <iostream>
// #include <map>
// #include <memory>
#include <numeric>
// #include <queue>
// #include <random>
// #include <ranges>
// #include <set>
// #include <sstream>
// #include <stack>
// #include <string>
// #include <tuple>
// #include <unordered_map>
// #include <unordered_set>
// #include <utility>
#include <vector>
#ifndef ONLINE_JUDGE
#define ___file_name "1"
#define ___debug_with_file
#else
// #define ___file_name ""
#endif
typedef int8_t i8;
typedef uint8_t u8;
typedef int16_t i16;
typedef uint16_t u16;
typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;

int n,m;
std::vector<i8> del;
std::vector<int> f,s;
class node{
public:
	int value,id;
	std::vector<node>::iterator son,sib;
	bool operator<(const node& other)const{
		return this->value==other.value?this->id<other.id:this->value<other.value;
	}
};
std::vector<node> t;
std::vector<node>::iterator nil,tot;
std::vector<std::vector<node>::iterator> root;

std::vector<node>::iterator meld(std::vector<node>::iterator u,std::vector<node>::iterator v){
	if(u==nil){
		return v;
	}else if(v==nil){
		return u;
	}
	if(!(*u<*v)){
		std::swap(u,v);
	}
	v->sib=u->son;
	u->son=v;
	return u;
}
std::vector<node>::iterator merge(std::vector<node>::iterator u){
	if(u==nil||u->sib==nil){
		return u;
	}
	return meld(merge(u->sib->sib),meld(u,u->sib));
}
int erase_min(std::vector<node>::iterator& u){
	int res(u->value);
	u=merge(u->son);
	return res;
}
int fd(int k){
	return f[k]==k?k:f[k]=fd(f[k]);
}
void ___main(){
	std::cin>>n>>m;
	t.resize(n+1);
	f.resize(n);
	std::iota(f.begin(),f.end(),0);
	s.resize(n);
	std::fill(s.begin(),s.end(),1);
	del.resize(n,0);
	nil=tot=t.begin();
	nil->son=nil->sib=nil;
	root.resize(n);
	for(int i(0);i<n;++i){
		root[i]=++tot;
		std::cin>>tot->value;
		tot->son=tot->sib=nil;
		tot->id=i;
	}
	for(int i(0),opt,u,v;i<m;++i){
		std::cin>>opt>>u;--u;
		if(opt==1){
			std::cin>>v;--v;
			if(!del[u]&&!del[v]){
				u=fd(u);v=fd(v);
				if(u!=v){
					if(s[u]<s[v]){
						u^=v^=u^=v;
					}
					f[v]=u;s[u]+=s[v];
					root[u]=meld(root[u],root[v]);
				}
			}
		}else{
			if(del[u]){
				std::cout<<"-1\n";
			}else{
				u=fd(u);
				std::cout<<root[u]->value<<'\n';
				del[root[u]->id]=1;
				erase_min(root[u]);
			}
		}
	}
}
int main(){
	std::cin.tie(nullptr)->sync_with_stdio(false);
#ifdef ___file_name
	std::ifstream input_file(___file_name".in");std::ofstream output_file(___file_name".out");
	std::streambuf *cinbuf(std::cin.rdbuf(input_file.rdbuf())),*coutbuf(std::cout.rdbuf(output_file.rdbuf()));
# ifdef ___debug_with_file
	std::ofstream debug_file(___file_name".debug");std::streambuf *cerrbuf(std::cerr.rdbuf(debug_file.rdbuf()));
# endif
#endif
	___main();
#ifdef ___file_name
	output_file.flush();std::cin.rdbuf(cinbuf);std::cout.rdbuf(coutbuf);
# ifdef ___debug_with_file
	debug_file.flush();std::cerr.rdbuf(cerrbuf);
# endif
#endif
	return 0;
}