前面一段是快读。 样例能过，又RE又WA。

#include <bits/stdc++.h>
using namespace std;
#define out(x) wrt(x),ptc(' ')
#define oun(x) wrt(x),ptc('\n')
#define gtc getchar()
#define ptc(x) putchar(x)
#define il inline
#define ll long long
#define rd read()
#define rdl readl()
il int read(){int x=0;bool f=0;char c=gtc;while(c<'0'||c>'9'){if(c=='-')f=1;c=gtc;}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gtc;return f?-x:x;}
il ll readl(){ll x=0;bool f=0;char c=gtc;while(c<'0'||c>'9'){if(c=='-')f=1;c=gtc;}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gtc;return f?-x:x;}
il void wt(ll x){if(x>9)wt(x/10);ptc(x%10+48);}
il void wrt(ll x){if(x<0)ptc('-'),x=-x;wt(x);}

const int N=20000010;
int a[1000010];
int t[N];

int rt[1000010];
int ls[N],rs[N];
int cnt=0;

int build(int o,int l,int r){
	o=++cnt;
	if(r<=l){t[o]=a[l];return o;}
	int m=l+r>>1;
	ls[o]=build(ls[o],l,m);
	rs[o]=build(rs[o],m+1,r);
	return o;
}

int upd(int o,int l,int r,int k,int x){
	int o1=++cnt;
	if(r<=l){t[o1]=x;return o1;}
	int m=l+r>>1;
	ls[o1]=ls[o],rs[o1]=rs[o];
	if(k<=m)ls[o1]=upd(ls[o],1,m,k,x);
	else rs[o1]=upd(rs[o],m+1,r,k,x);
	return o1;
}

int que(int o,int l,int r,int k){
	if(r<=l)return t[o];
	int m=l+r>>1;
	if(k<=m)return que(ls[o],l,m,k);
	else return que(rs[o],m+1,r,k);
}

signed main(){
	
	int n=rd,q=rd;
	for(int i=1;i<=n;i++)a[i]=rd;
	
	int tot=0;
	rt[0]=build(0,1,n);
	for(int i=1;i<=q;i++){
		int root=rd,op=rd,k=rd;
		if(op==1){
			int w=rd;
			rt[i]=upd(rt[root],1,n,k,w);
		}else{
			oun(que(rt[root],1,n,k));
			rt[i]=rt[root];
		}
	}
	
	return 0;
}