#include <bits/stdc++.h>
#define pii pair<int,int>
#define s1 first
#define s2 second
#define N 200011
using namespace std;
int q,k,m,n,pw[55];
struct num{int a[26];num(){memset(a,0,sizeof(a));}num(int _x){for(int i=0;i<m;++i)a[i]=_x/pw[i]%k;}int& operator[](int x){return a[x];}};
num operator+(num a,num b){num c;for(int i=0;i<m;++i)c[i]=(a[i]+b[i])%k;return c;}
num operator-(num a,num b){num c;for(int i=0;i<m;++i)c[i]=(a[i]+k-b[i])%k;return c;}
num operator*(num a,int v){num c;for(int i=0;i<m;++i)c[i]=1ll*a[i]*v%k;return c;}
num operator*(int v,num a){num c;for(int i=0;i<m;++i)c[i]=1ll*a[i]*v%k;return c;}
int fa[N][18],dep[N];num faw[N][18];
num bs[55];
pair<num,num> red(num a,num b,int id)
{
	if(!b[id])return {a,b};
	return red(b,a-(a[id]/b[id])*b,id);
}
void ins(num x);
void sift();
void Ins(num x)
{
	ins(x);
	sift();
}
void ins(num x)
{
	for(int i=m-1;~i;--i)if(x[i])
	{
		if(bs[i][i])
		{
			auto tt=red(bs[i],x,i);
			bs[i]=tt.s1;x=tt.s2;
		}
		else
		{
			bs[i]=x;break;
		}
	}
}
void sift()
{
	for(int i=m-1;~i;--i)if(bs[i][i])
	{
		ins(bs[i]*(k/gcd(bs[i][i],k)));
	}
}
num query(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	num ans;
	for(int i=17;~i;--i)if(dep[x]-(1<<i)>=dep[y])ans=ans+faw[x][i],x=fa[x][i];if(x==y)return ans;
	for(int i=17;~i;--i)if(fa[x][i]^fa[y][i])ans=ans+faw[x][i]+faw[y][i],x=fa[x][i],y=fa[y][i];return ans+faw[x][0]+faw[y][0];
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void exgcd(int a,int b,int &x,int &y)
{
	if(!b){x=1;y=0;return;}
	exgcd(b,a%b,y,x);y-=(a/b)*x;
}
num search(num x)
{
	for(int i=m-1;~i;--i)if(bs[i][i])
	{
		int g=gcd(k,bs[i][i]);
		int y=x[i]%g;
		int kk,t;
		exgcd(bs[i][i],k,kk,t);
		kk=((kk*(y-x[i])/g)%k+k)%k;
		x=x+kk*bs[i];
	}
	return x;
}
int main()
{
	scanf("%d%d%d",&q,&k,&m);
	pw[0]=1;for(int i=1;i<=m;++i)pw[i]=pw[i-1]*k;
	n=1;
	for(int i=1;i<=q;++i)
	{
		int cmd,x,y;
		scanf("%d%d%d",&cmd,&x,&y);
		if(cmd==1)
		{
			++n;
			fa[n][0]=x;faw[n][0]=y;dep[n]=dep[x]+1;
			for(int i=1;i<=17;++i)fa[n][i]=fa[fa[n][i-1]][i-1],faw[n][i]=faw[n][i-1]+faw[fa[n][i-1]][i-1];
			Ins((num)y+(num)y);
		}
		else if(cmd==2)
		{
			int v;scanf("%d",&v);
			Ins(query(x,y)+v);
		}
		else
		{
			if(k%2==1)printf("0\n");
			else
			{
				num val=query(x,y);
				num ans=search(query(x,y));
				int h=0;
				for(int i=0;i<m;++i)h+=pw[i]*ans[i];
				printf("%d\n",h);
			}
		}
	}
	fclose(stdin);fclose(stdout);return 0;
}