求条（40pts，AC了#5之前的所有）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll cnt;
struct tree{
	ll v,ls,rs;
}t[30000005];
void add(ll id,ll la,ll l,ll r,ll v,ll x)
{
	if(l==r)
	{
		t[id].v=v;
		return;
	}
	ll mid=l+r>>1;
	if(mid>=x)
	{
		t[id].ls=++cnt; t[id].rs=t[la].rs;
		add(t[id].ls,t[la].ls,l,mid,v,x);
	}
	else
	{
		
		t[id].ls=t[la].ls; t[id].rs=++cnt;
		add(t[id].rs,t[la].rs,mid+1,r,v,x);
	}
	return;
}
ll fid(ll id,ll l,ll r,ll x)
{
	if(l==r) return t[id].v;
	ll mid=l+r>>1;
	if(mid>=x) return fid(t[id].ls,l,mid,x);
	else return fid(t[id].rs,mid+1,r,x);
}
void build(ll id,ll l,ll r)
{
	if(l==r)
	{
		cin>>t[id].v;
		return;
	}
	t[id].ls=id<<1; t[id].rs=id<<1|1;
	ll mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	return;
}
ll n,m,la,opt,x,v,i,p[1000005];
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	build(1,1,n);
	cnt=2*n-1; p[0]=1;
	for(i=1;i<=m;i++)
	{
		cin>>la>>opt>>x;
		p[i]=++cnt;
		if(opt==1)
		{
			cin>>v;
			add(cnt,p[la],1,n,v,x);
		}
		if(opt==2)
		{
			t[cnt].ls=t[p[i-1]].ls; t[cnt].rs=t[p[i-1]].rs;
			cout<<fid(p[la],1,n,x)<<"\n";
		}
	}
    return 0;
}