#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,B=20;
int q,k,m;
int fa[N][B],dep[N];
inline int LCA(int u,int v)
{
	if(dep[u]>dep[v])swap(u,v);
	int D=dep[v]-dep[u];
	if(D)for(int i=__lg(D);~i;--i)if(D>>i&1)v=fa[v][i];
	if(u==v)return u;
	for(int i=__lg(dep[u]);~i;--i)
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
inline int add(int x,int y){int z=0,p=1;while(x||y)z+=(x%k+y%k)%k*p,x/=k,y/=k,p*=k;return z;}
inline int dec(int x,int y){int z=0,p=1;while(x||y)z+=(x%k+k-y%k)%k*p,x/=k,y/=k,p*=k;return z;}
inline int mul(int x,int w){int z=0,p=1;while(x   )z+=(x%k*w)%k*p,x/=k,p*=k;return z;}
int Base[25];
void ini(){Base[0]=1;for(int i=1;i<=m;++i)Base[i]=Base[i-1]*k;}
inline int get(int x,int i){return x/Base[i]%k;}
inline int exgcd(int a,int b,int&x,int&y)
{
	if(!b){x=1,y=0;return a;}
	int d=exgcd(b,a%b,y,x);y-=a/b*x;
	return d;
}
namespace Basis
{
	int a[N];
	inline void ins(int x)
	{
		for(int i=m-1,w;~i;--i)if(w=get(x,i))
		{
			if(!a[i])
			{
				int p,q,d=exgcd(get(x,i),k,p,q);
				a[i]=mul(x,p);x=mul(x,k/d);
			}
			else
			{
				while(get(x,i))
				{
					int d=get(a[i],i)/get(x,i);
					dec(a[i],mul(x,d));
					swap(x,a[i]);
				}
			}
		}
	}
	inline int ask(int x)
	{
		for(int i=m-1;~i;--i)
		{
			int u=get(x,i);
			if(u&&a[i])x=dec(x,mul(a[i],u/get(a[i],i)));
		}
		return x;
	}
}
int val[N],tt=1;
int main()
{
cin.tie(0)->sync_with_stdio(0);
	cin>>q>>k>>m;
	ini();
	while(q--)
	{
		int o,x,y,v;cin>>o;
		if(o==1)
		{
			int x,v;cin>>x>>v;
			val[++tt]=add(val[x],v);
			dep[tt]=dep[x]+1;
			fa[tt][0]=x;
			for(int i=1;i<B;++i)fa[tt][i]=fa[fa[tt][i-1]][i-1];
			Basis::ins(mul(v,2));
		}
		else if(o==2)
		{
			cin>>x>>y>>v;
			Basis::ins(add(dec(add(val[x],val[y]),mul(val[LCA(x,y)],2)),v));
		}
		else
		{
			cin>>x>>y;
			cout<<Basis::ask(dec(add(val[x],val[y]),mul(val[LCA(x,y)],2)))<<"\n";
		}
	}
}