#include<bits/stdc++.h>
#define T HJTsegmentTreeNodes
#define Rt HJTsegmentTreeRoots
using namespace std;
struct HJTsegmentTreeNode{
    int l,r,v;
    HJTsegmentTreeNode *ls,*rs;
};
typedef HJTsegmentTreeNode Node;
struct HJTsegmentTree{
    Node HJTsegmentTreeNodes[4000005];
    Node* HJTsegmentTreeRoots[1000005];
    int siz,rtcnt;
    inline Node* newNode(){return &T[++siz];}
    inline Node* getRoot(int id){return Rt[id];}
    inline int size(){return siz;}
    inline int countVersion(){return rtcnt;}
    inline Node* newVersion(){
        Node* root=&T[++siz];
        Rt[++rtcnt]=root;
        return root;
    }
    inline Node* newVersion(int l,int r){
        Node* root=&T[++siz];
        Rt[++rtcnt]=root;
        root->l=l;
        root->r=r;
        return root;
    }
    inline Node* newVersion(Node* node){
        return Rt[++rtcnt]=node;
    }
    inline void init(Node* rt,int l,int r,int* arr){
        rt->l=l;
        rt->r=r;
        if (l==r){
            rt->v=arr[l];
            return;
        }
        int mid=(l+r)>>1;
        rt->ls=newNode();
        init(rt->ls,l,mid,arr);
        rt->rs=newNode();
        init(rt->rs,mid+1,r,arr);
    }
    inline Node* cloneNode(Node* node){
        Node* cl=newNode();
        cl->l=node->l;
        cl->r=node->r;
        cl->ls=node->ls;
        cl->rs=node->rs;
        cl->v=node->v;
        return cl;
    }
    inline Node* update(Node* rt,int x,int val){
        Node* newrt=cloneNode(rt);
        if (newrt->l==newrt->r){
            newrt->v=val;
            return newrt;
        }
        int mid=(newrt->l+newrt->r)>>1;
        if (x<=mid){
            update(newrt->ls,x,val);
        }
        else{
            update(newrt->rs,x,val);
        }
        return newrt;
    }
    inline int query(Node* rt,int x){
        if (rt->l==rt->r)return rt->v;
        int mid=(rt->l+rt->r)>>1;
        if (x<=mid)return query(rt->ls,x);
        else return query(rt->rs,x);
    }
}HJT;
int a[100005];
int main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++)cin>>a[i];
    HJT.init(HJT.newVersion(1,n),1,n,a);
    for (int i=1;i<=m;i++){
        int ver,op,x,y;
        cin>>ver>>op>>x;
        ++ver;
        if (op==1){
            cin>>y;
            HJT.newVersion(HJT.update(HJT.getRoot(ver),x,y));
        }
        else{
            Node* verr=HJT.getRoot(ver);
            cout<<HJT.query(verr,x)<<endl;
            HJT.newVersion(verr);
        }
    }
    return 0;
}