rt，这个题 我用cchash和umap都能过但是用gphash #5直接满了几百倍，求大佬解答。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll unsigned long long
using namespace std;
using namespace __gnu_pbds;
namespace IO
{
	char buff[1<<21],*p1=buff,*p2=buff;
	char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
	template<typename T>void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
	template<typename T>void read_s(T &x){char ch=getch();while(ch<'a'||ch>'z')ch=getch();while(ch>='a'&&ch<='z'){x+=ch;ch=getch();}}
	template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
	char ch[100];
	template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
	template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);write(args...);}
	void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
	void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
int n,m,q;
vector<int>e[500005];
ll Pow[500005];
ll a[500005];
int f[500005];
ll h[500005];
const ll base=(2e6+3);
cc_hash_table<ll,int>mp;
//unordered_map<ll,int>mp;
void dfs(int u)
{
	mp[h[u]]=u;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		h[v]=h[u]*base+i+1;
		dfs(v);
	}
}
namespace Nene
{
	struct segt
	{
		int len;
		ll val;
		inline segt operator+(const segt &a)const
		{
			segt res;
			res.len=len+a.len;
			res.val=val*Pow[a.len]+a.val;
			return res;
		}
	}t[500005<<2];
	#define ls (root<<1)
	#define rs (root<<1|1)
	#define mid (l+r>>1)
	void insert(int x,ll v,int root=1,int l=1,int r=m)
	{
		if(l==r) return t[root].val=v,t[root].len=1,void();
		if(x<=mid) insert(x,v,ls,l,mid);
		else insert(x,v,rs,mid+1,r);
		t[root]=t[ls]+t[rs];
	}
	vector<int>rt(100),tl(100),tr(100);
	void get(int x,int y,int root=1,int l=1,int r=m)
	{
		if(l>=x&&r<=y) return rt.push_back(root),tl.push_back(l),tr.push_back(r),void();
		if(x<=mid) get(x,y,ls,l,mid);
		if(y>mid) get(x,y,rs,mid+1,r);
	}
	const ll f1=18446744073709551615ull;
	ll find(ll now,int root,int l,int r)
	{
		if(mp.find(now)==mp.end()) return f1;
		if(l==r) return mp.find(now*base+t[root].val)==mp.end()?now:now*base+t[root].val;
		if(mp.find(now*Pow[t[ls].len]+t[ls].val)==mp.end()) return find(now,ls,l,mid);
		return find(now*Pow[t[ls].len]+t[ls].val,rs,mid+1,r);
	}
	inline ll query(int p,int x,int y)
	{
		rt.clear();tl.clear();tr.clear();
		ll now=h[p];
		get(x,y);
		for(int i=0;i<rt.size();i++)
		{
			if(mp.find(now*Pow[t[rt[i]].len]+t[rt[i]].val)==mp.end()) 
			{
				ll tmp=find(now,rt[i],tl[i],tr[i]);
				return tmp==f1?p:mp[tmp];
			}
			now=now*Pow[t[rt[i]].len]+t[rt[i]].val;
		}
		return mp[now];
	}
	#undef mid
}using namespace Nene;
int main()
{
//	freopen("P5537_5.in","r",stdin);
//	freopen(".out","w",stdout);
	read(n,m,q);
	int rt;
	for(int i=1;i<=n;i++) 
	{
		read(f[i]);
		if(!f[i]) rt=i;
		else e[f[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end());
	Pow[0]=1;
	for(int i=1;i<=500000;i++) Pow[i]=Pow[i-1]*base;
	dfs(rt);
	for(int i=1;i<=m;i++) read(a[i]),insert(i,a[i]);
	while(q--)
	{
		int op,x,ql,qr;read(op,x,ql);
		if(op==1) read(qr),write(query(x,ql,qr)),putch('\n');
		else insert(x,ql),a[x]=ql;
	}
	flush();
	return 0;
}