#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][21],dep[N];num faw[N][21];
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)
{//printf("ins(");for(int i=0;i<m;++i)printf("%d ",x.a[i]);printf(")\n");
	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;}
	}
}
num query(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	num ans;
	for(int i=20;~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=20;~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)
{
	// printf("search(");for(int i=m-1;~i;--i)printf("%d ",x[i]);printf(")\n");
	// printf("bs:\n");
	// for(int i=m-1;~i;--i)
	// {
	// 	for(int j=m-1;~j;--j)printf("%d ",bs[i][j]);putchar(10);
	// }
	for(int i=m-1;~i;--i)if(bs[i][i])
	{
		int g=gcd(k,bs[i][i]);
		int y=x[i]%g;//printf("i:%d g:%d y:%d\n",i,g,y);
		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)
	{//printf("------------------------------------------\n");
		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<=20;++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];
			// for(int i=0;(1<<i)<dep[n];++i)
			// {
			// 	printf("faw[%d]:",i);for(int j=0;j<m;++j)printf("%d ",faw[n][i][j]);putchar(10);
			// }
			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);
				// printf("val:");for(int i=0;i<m;++i)printf("%d ",val[i]);putchar(10);
				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;
}