代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 4;
struct T {
	int l,r,v;
}t[maxn*40]; 
int a[maxn],edition[maxn*40],tot;
int build(int l,int r)
{
	int p=++tot;
	if(l==r) {
		t[p].v=a[l]; return p;
	}
	int mid=(l+r)>>1;
	t[p].l=build(l,mid);
	t[p].r=build(mid+1,r);
	return p;
}
int update(int id,int l,int r,int k,int val)
{
	int p=++tot;
	if(l==r) {
		t[p].v=val; return p;
	}
	int mid=(l+r)>>1;
	t[p].l=t[id].l,t[p].r=t[id].r;
	if(k<=mid) t[p].l=update(t[p].l,l,mid,k,val);
	else t[p].r=update(t[p].r,mid+1,r,k,val);
 	return p;
}
int query(int id,int l,int r,int k)
{
	if(l==r) return t[id].v;
	int mid=(l+r)>>1;
	if(k<=mid) return query(t[id].l,l,mid,k);
	else return query(t[id].r,mid+1,r,k);
}
int main()
{
	int n,m,id,op,k,val;
	scanf("%d%d",&n,&m); 
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,n);
	edition[0]=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&id,&op,&k);
		if(op==1) {
			scanf("%d",&val);
			edition[i]=update(edition[id],1,n,k,val);
		}
		else {
			edition[i]=edition[id];
			printf("%d\n",query(edition[id],1,n,k));
		}
	}
	return 0;
}