#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const maxn=1e5+;

int n,m,rt[maxn],fa[maxn];

bool out[maxn];

struct N{

    int ls,rs,val,dis;

}t[maxn];

int get(int x){while(rt[x])x=rt[x]; return x;}

int merge(int x,int y)

{

    if(!x||!y)return x+y;

    if(t[x].val>t[y].val||(t[x].val==t[y].val&&x>y))swap(x,y);

    t[x].rs=merge(t[x].rs,y);

    if(t[t[x].ls].dis<t[t[x].rs].dis)swap(t[x].ls,t[x].rs);

    if(t[x].rs)t[x].dis=t[t[x].rs].dis+;

    else t[x].dis=;

    rt[t[x].ls]=rt[t[x].rs]=x;

    return x;

}

void del(int x)

{

    out[x]=;

    rt[t[x].ls]=rt[t[x].rs]=;

    merge(t[x].ls,t[x].rs);

}

int main()

{

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

    for(int i=,x;i<=n;i++){scanf("%d",&x); t[i].val=x;}

    for(int i=,op,x,y,u,v;i<=m;i++)

    {

        scanf("%d%d",&op,&x);

        if(op==)

        {

            scanf("%d",&y);

            if(out[x]||out[y])continue;

            u=get(x); v=get(y);

            if(u==v)continue;

            merge(u,v);

        }

        else

        {

            if(out[x]){printf("-1\n"); continue;}

            u=get(x); printf("%d\n",t[u].val);

            del(u);

        }

    }

    return ;

}