记录

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
ll top = 0;
ll a[1000010];
ll root[1000010];
struct node{
    ll l,r,v;
}t[4000010];
inline ll clone(ll p){
    t[++top] = t[p];
    return top;
}
inline ll build(ll p,ll l,ll r){
    p = ++top;
    if(l == r){
        t[p].v = a[l];
        return p;
    }
    ll mid = (l + r) >> 1;
    t[p].l = build(t[p].l,l,mid);
    t[p].r = build(t[p].r,mid + 1,r);
    return p;
}
inline ll edit(ll p,ll l,ll r,ll x,ll k){
    p = clone(p);
    if(l == r){
        t[p].v = k;
        return p;
    }
    ll mid = (l + r) >> 1;
    if(x <= mid)t[p].l = edit(t[p].l,l,mid,x,k);
    if(mid < x)t[p].r = edit(t[p].r,mid + 1,r,x,k);
    return p;
}
inline ll ask(ll p,ll l,ll r,ll x){
    if(l == r)return t[p].v;
    ll mid = (l + r) >> 1;
    if(x <= mid)return ask(t[p].l,l,mid,x);
    if(mid < x)return ask(t[p].r,mid + 1,r,x);
}
namespace io{
    inline long long read(){
        long long x = 0,f = 1;
        char c = getchar();
        while(c < '0' || c > '9'){
            if(c == '-')f = -1;
            c = getchar();
        }
        while(c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = getchar();
        }
        return x * f;
    }
    inline void write(long long x){
        if(x == 0)putchar('0');
        if(x < 0)putchar('-');
        x = x > 0 ? x : -x;
        char F[200];
        long long cnt = 0;
        while(x){
            F[cnt++] = x % 10 + 48;
            x /= 10;
        }
        while(cnt)putchar(F[--cnt]);
        putchar('\n');
        return ;
    }
}
using namespace io;
signed main(){
    n = read(),m = read();
    for(ll i = 1;i <= n;i++)a[i] = read();
    root[0] = build(0,1,n);
    for(ll i = 1;i <= m;i++){
        ll v = read(),mode = read(),loc = read();//v = version loc = index
        if(mode == 1)root[i] = edit(root[v],1,n,loc,read());
        else{
            write(ask(root[v],1,n,loc));
            root[i] = root[v];
        }
    }
    return 0;
}