#include <bits/stdc++.h>
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;
}
void exgcd(int a,int b,int &x,int &y)
{
	if(b==0) return x=1,y=0,void();
	else exgcd(b,a%b,y,x),y-=a/b*x,void();
}
int Q,k,m;
struct Vector{
	int num[25];
	Vector operator+(const Vector A) const
	{
		Vector ret;
		for(int i=0;i<m;i++)
		{
			ret.num[i]=num[i]+A.num[i];
			if(ret.num[i]>=k) ret.num[i]-=k;
		}
		return ret;
	}
	Vector operator-(const Vector A)const
	{
		Vector ret;
		for(int i=0;i<m;i++)
		{
			ret.num[i]=num[i]-A.num[i];
			if(ret.num[i]<0) ret.num[i]+=k;
		}
		return ret;
	}
	Vector operator*(const int A)const
	{
		Vector ret;int a=A%k;while(a<0) a+=k;
		for(int i=0;i<m;i++)
			ret.num[i]=1ll*num[i]*a%k;
		return ret;
	}
	void input(int x)
	{
		for(int i=0;i<m;i++)
			num[i]=x%k,x/=k;
	}
	int output()
	{
		int ret=0;
		for(int i=m-1;~i;i--)
			ret=ret*k+num[i];
		return ret;
	}
};
Vector bas[30];bool hv[30];
void ins(Vector X)
{
	int x,y;
	for(int i=m-1;~i;i--) if(X.num[i])
	{
		if(hv[i])
		{
			if(__gcd(X.num[i],bas[i].num[i])<bas[i].num[i])
			{
				exgcd(X.num[i],bas[i].num[i],x,y);
				bas[i]=X*x+bas[i]*y;
			}
			X=X-bas[i]*(X.num[i]/bas[i].num[i]);
		}
		else
		{
			exgcd(X.num[i],k,x,y);
			hv[i]=true,bas[i]=X*x;
			return;
		}
	}
}
Vector calc(Vector X)
{
	for(int i=m-1;~i;i--) if(X.num[i]&&hv[i])
		X=X-bas[i]*(X.num[i]/bas[i].num[i]);
	return X;
}
int op,x,y,v,n,lca;
int dep[200010],fa[20][200010];
Vector tmp,val[200010];
inline int get_lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=19;~i;i--) if(dep[fa[i][u]]>=dep[v])
		u=fa[i][u];
	for(int i=19;~i;i--) if(fa[i][u]!=fa[i][v])
		u=fa[i][u],v=fa[i][v];
	return u!=v?u:fa[0][u];
}
int main()
{
	Q=Qread(),k=Qread(),m=Qread();
	
	if(k&1)
	{
		for(int i=1;i<=Q;i++)
		{
			op=Qread();
			if(op==1) x=Qread(),v=Qread();
			else if(op==2) x=Qread(),y=Qread(),v=Qread();
			else x=Qread(),y=Qread(),printf("0\n");
		}
		return 0;
	}
	
	n=1;
	for(int i=1;i<=Q;i++)
	{
		op=Qread();
		if(op==1)
		{
			x=Qread(),v=Qread();
			fa[0][++n]=x;
			for(int i=1;i<20;i++)
				fa[i][n]=fa[i-1][fa[i-1][n]];
			tmp.input(v);
			val[n]=val[x]+tmp,dep[n]=dep[x]+1;
			ins(tmp*2);
		}
		else if(op==2)
		{
			x=Qread(),y=Qread(),v=Qread();
			lca=get_lca(x,y);
			tmp.input(v);
			tmp=tmp+val[x]+val[y]-val[lca]-val[lca];
			ins(tmp);
		}
		else
		{
			x=Qread(),y=Qread();
			lca=get_lca(x,y);
			tmp=val[x]+val[y]-val[lca]-val[lca];
			tmp=calc(tmp);
			printf("%d\n",tmp.output());
		}
	}
	return 0;
}