#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;
int n,m;
struct nod
{
    int l,r;
};
int vl[10000010];
vector<nod>d;
int rt[10000010];
void build(int l,int r)
{
    if(l==r)
    {
        d.push_back((nod){vl[l],vl[l]});
        return;
    }
    int i=d.size();
    d.push_back((nod){i+1,0});
    build(l,(l+r>>1));
    d[i].r=d.size();
    build((l+r>>1)+1,r);
}
void chang(int ver,int p,int v)
{
    int l=1,r=n,mid,i=d.size(),j=rt[ver];
    while(l<r)
    {
        i++;
        mid=(l+r>>1);
        if(p<=mid)
        {
            r=mid;
            d.push_back((nod){i,d[j].r});
            j=d[j].l;
        }
        else
        {
            l=mid+1;
            d.push_back((nod){d[j].l,i});
            j=d[j].r;
        }
    }
    d.push_back((nod){v,v});
}
int query(int ver,int p)
{
    int l=1,r=n,mid,j=rt[ver];
    while(l<r)
    {
        mid=(l+r>>1);
        if(p<=mid)
        {
            r=mid;
            j=d[j].l;
        }
        else
        {
            l=mid+1;
            j=d[j].r;
        }
    }
    return d[j].l;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&vl[i]);
    }
    build(1,n);
    for(int i=1;i<=m;i++)
    {
        int ver,op,x,y;
        scanf("%lld%lld%lld",&ver,&op,&x);
        if(op==1)
        {
            scanf("%lld",&y);
            rt[i]=d.size();
            chang(ver,x,y);
        }
        if(op==2)
        {
            rt[i]=rt[i-1];
            printf("%lld\n",query(ver,x));
        }
    }
    return 0;
}

RT

58分还看不到别人代码qwq