#include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 inline int rd(){

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-; c=getchar();}

     while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

     return f*x;

 }

 const int maxn=(1e6)+,maxm=maxn;

 int N,M,num_treenode=,root[maxm],belong_root[maxm],num_root=,u,num_version=,A[maxn],V,loc,o,val;

 struct Tree{

     int ls,rs,l,r,data;

 }t[(maxn<<)+*maxm];

 inline void Build(int x,int l,int r){

     t[x].l=l;t[x].r=r;

     if(l==r){

         t[x].data=A[l];

         return;

     }

     int mid=(l+r)>>;

     t[x].ls=++num_treenode;Build(num_treenode,l,mid);

     t[x].rs=++num_treenode;Build(num_treenode,mid+,r);

     return;

 }

 inline void Update(int x,int u,int loc,int v){

     int l=t[u].l,r=t[u].r,mid=(l+r)>>;

     t[x].l=l;t[x].r=r;

     if(l==r&&l==loc){

         t[x].data=v;

         return;

     }

     if(loc<=mid){

         t[x].rs=t[u].rs;

         t[x].ls=++num_treenode;

         Update(num_treenode,t[u].ls,loc,v);

     }

     else{

         t[x].ls=t[u].ls;

         t[x].rs=++num_treenode;

         Update(num_treenode,t[u].rs,loc,v);

     }

     return;

 }

 inline int Query(int x,int loc){

     int l=t[x].l,r=t[x].r,mid=(l+r)>>;

     if(l==r&&l==loc) return t[x].data;

     if(loc<=mid)return Query(t[x].ls,loc);

     else return Query(t[x].rs,loc);

 }

 int main(){

     N=rd();M=rd();

     for(int i=;i<=N;i++)A[i]=rd();

     root[++num_root]=++num_treenode;//root[i]数组记录树i的根节点是哪个

     belong_root[]=num_root;//belong_root[i]记录版本i的树根是哪个

     Build(num_treenode,,N);

     while(M--){

         V=rd();o=rd();loc=rd();

         u=belong_root[V];//u记录第V个版本到底属于哪颗树

         if(o==){

             val=rd();

             root[++num_root]=++num_treenode;//多了一颗树

             Update(num_treenode,root[u],loc,val);

             belong_root[++num_version]=num_root;

         }

         else{

             printf("%d\n",Query(root[u],loc));

             belong_root[++num_version]=u;

         }

     }

     return ;

 }