#include<bits/stdc++.h>
#define ll long long
#define N 200010
using namespace std;
int q,k,m,tot,fa[N],s1[N][19],bz[30],x,y,v,dep[N],tol;
struct node{int f[30];}fb[N],c,s2[N][19],cir,sum,b[30];
ll ans;
node mul(node a,int x){
	for(int i=1;i<=m;i++)c.f[i]=(1ll*a.f[i]*x%k+k)%k;
	return c;
}
node add(node a,node b){
	for(int i=1;i<=m;i++)c.f[i]=(a.f[i]+b.f[i])%k;
	return c; 
}
node lca(int x,int y){
	node sum;
	for(int i=1;i<=m;i++)sum.f[i]=0;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=18;i>=0;i--)
	if(dep[s1[x][i]]>=dep[y]){
		sum=add(sum,s2[x][i]);x=s1[x][i];
	}
	for(int i=18;i>=0;i--)
	if(s1[x][i]!=s1[y][i]){
		sum=add(sum,s2[x][i]);x=s1[x][i];
		sum=add(sum,s2[y][i]);y=s1[y][i];
	}if(x!=y){sum=add(sum,fb[x]);sum=add(sum,fb[y]);}
	return sum;
}
int gcd(int n,int m){return (m==0)?n:gcd(m,n%m);}
void exgcd(int n,int m,int &x,int &y){
	if(m==0){x=1;y=0;return;}
	exgcd(m,n%m,y,x);
	y=y-(n/m)*x;
}
int get(int v){
	int x=0,y=0;
	exgcd(v,k,x,y);
	return (x+k)%k;
}
void insert(node a){
	for(int i=m;i>=1;i--)
	if(a.f[i]){
		if(!bz[i]){
			b[i]=mul(a,get(a.f[i]));bz[i]=1;
			a=mul(a,k/gcd(k,a.f[i]));
		}
		while(a.f[i]){
			int v=b[i].f[i]/a.f[i];
			b[i]=add(b[i],mul(a,-v));
			swap(b[i],a);
		}
	} 
}
node find(node a){
	for(int i=m;i>=1;i--)
	if(bz[i]){
		a=add(a,mul(b[i],-(a.f[i]/b[i].f[i])));
	}return a;
}
int main(){
	scanf("%d%d%d",&q,&k,&m);tot=1;dep[1]=1;
	for(;q;q--){
		scanf("%d",&tol);
		if(tol==1){
			scanf("%d%d",&x,&v);
			tot++;fa[tot]=x;dep[tot]=dep[x]+1;
			for(int i=1;i<=m;i++)
			fb[tot].f[i]=v%k,v/=k;
			insert(mul(fb[tot],2));
			s1[tot][0]=fa[tot];s2[tot][0]=fb[tot];
			for(int i=1;i<=18;i++)
			s1[tot][i]=s1[s1[tot][i-1]][i-1],
			s2[tot][i]=add(s2[tot][i-1],s2[s1[tot][i-1]][i-1]);
		}else if(tol==2){
			scanf("%d%d%d",&x,&y,&v);
			for(int i=1;i<=m;i++)
			cir.f[i]=v%k,v/=k;
			cir=add(cir,lca(x,y));
			insert(cir);
		}else if(tol==3){
			scanf("%d%d",&x,&y);
			sum=find(lca(x,y));ans=0;
			for(int i=m;i>=1;i--)ans=ans*k+sum.f[i];
			printf("%lld\n",ans);
		}
	}
}