1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 #define K 1000

 5 #define bl(k) ((k-1)/K)

 6 struct ji{

 7     int nex,to;

 8 }edge[N];

 9 vector<int>v[N];

10 int E,n,m,p[N],a[N],x[N],y[N],b[N],head[N],sz[N],fa[N],ans[N],f[N][105];

11 bool cmp(int x,int y){

12     return a[x]<a[y];

13 }

14 void add(int x,int y){

15     edge[E].nex=head[x];

16     edge[E].to=y;

17     head[x]=E++;

18 }

19 int find(int k){

20     if (k==fa[k])return k;

21     return find(fa[k]);

22 }

23 int query(int k){

24     x[k]=find(x[k]);

25     for(int i=0;i<=bl(n);i++)

26         if (y[k]>f[x[k]][i])y[k]-=f[x[k]][i];

27         else

28             for(int j=i*K+1;j<=(i+1)*K;j++)

29                 if ((find(b[j])==x[k])&&(--y[k]==0))return a[b[j]];

30     return -1;

31 }

32 void add(int k){

33     x[k]=find(x[k]);

34     y[k]=find(y[k]);

35     if (x[k]==y[k])return;

36     if (sz[x[k]]>sz[y[k]])swap(x[k],y[k]);

37     fa[x[k]]=y[k];

38     sz[y[k]]+=sz[x[k]];

39     for(int i=0;i<=bl(n);i++)f[y[k]][i]+=f[x[k]][i];

40 }

41 void del(int k){

42     if (x[k]==y[k])return;

43     fa[x[k]]=x[k];

44     sz[y[k]]-=sz[x[k]];

45     for(int i=0;i<=bl(n);i++)f[y[k]][i]-=f[x[k]][i];

46 }

47 void dfs(int k){

48     if (p[k]==1)add(k);

49     if (p[k]==3)ans[k]=query(k);

50     for(int i=head[k];i!=-1;i=edge[i].nex)dfs(edge[i].to);

51     if (p[k]==1)del(k);

52 }

53 int main(){

54     scanf("%d%d",&n,&m);

55     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

56     memset(head,-1,sizeof(head));

57     for(int i=1;i<=n;i++)fa[i]=b[i]=i;

58     sort(b+1,b+n+1,cmp);

59     for(int i=1;i<=n;i++)sz[i]=f[b[i]][bl(i)]=1;

60     for(int i=1;i<=m;i++){

61         scanf("%d%d",&p[i],&x[i]);

62         if (p[i]==2)add(x[i],i);

63         else{

64             scanf("%d",&y[i]);

65             add(i-1,i);

66         }

67     }

68     dfs(0);

69     for(int i=1;i<=m;i++)

70         if (p[i]==3)printf("%d\n",ans[i]);

71 }