#include<iostream>
#include<cstdio>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
int read(){
	int u=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9'){
		u=u*10+c-48;
		c=getchar();
	}
	return u;
}
int q,K,m,er[30],n=1;
int gcd(int x,int y){
	if(!y)return x;
	return gcd(y,x%y);
}
int add(int x,int y){
	int u=0;
	fo(i,0,m-1){
		u+=((x/er[i]%K)+(y/er[i]%K))%K*er[i];
	}
	return u;
}
int cf(int x,int y){
	int u=0;
	fo(i,0,m-1){
		u+=((x/er[i]%K)*y%K+K)%K*er[i];
	}
	return u;
}
ll h=0;
pair<ll,ll> kgcd(ll x,ll y){
	if(!y)return {h,0};
	pair<ll,ll>u=kgcd(y,x%y);
	return {u.second,u.first-u.second*(x/y)};
}
int B[33];
int fa[19][200011],deep[200011];
int c[200011];
void check(int i){
	if(K%(B[i]/er[i])!=0){
		h=gcd(K,B[i]);
		pair<ll,ll>u=kgcd(B[i]/er[i],K);
		u.first%=K;
		B[i]=cf(B[i],u.first);
	} 
}
void Ins(int x){
	fod(i,m-1,0){
		if(x/er[i]>0){
			if(!B[i]){
				B[i]=x;
				x=cf(x,K/gcd(x/er[i],K));
			}
			while(x/er[i]>0){
				int u=(B[i]/er[i])/(x/er[i]),v=0;
				v=add(B[i],cf(x,-u));
				B[i]=x,x=v;
			}
			check(i);
		}
	}
}
int find(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	fod(i,18,0){
		if(deep[fa[i][x]]>=deep[y])x=fa[i][x];
	}
	if(x==y)return x;
	fod(i,18,0){
		if(fa[i][x]&&fa[i][x]!=fa[i][y])
		x=fa[i][x],y=fa[i][y];
	}
	return fa[0][x];
}
int main(){
	q=read();
	K=read();
	m=read();
	er[0]=1;
	fo(i,1,m)er[i]=er[i-1]*K;
	deep[1]=1;
	while(q){
		--q;
		int opt=read();
		if(opt==1){
			int x=read(),v=read();
			fa[0][++n]=x;
			fo(i,1,18)fa[i][n]=fa[i-1][fa[i-1][n]];
			deep[n]=deep[x]+1;
			c[n]=add(c[x],v);
			Ins(cf(v,2));
		}
		if(opt==2){
			int x=read(),y=read(),v=read();
			int lca=find(x,y),u=0;
			fo(i,0,m-1){
				u+=((c[x]/er[i]%K)+(c[y]/er[i]%K)+(v/er[i]%K)-(c[lca]/er[i]*2%K)+K)%K*er[i];
			}
			Ins(u);
		}
		if(opt==3){
			int x=read(),y=read();
			int lca=find(x,y),u=0;
			fo(i,0,m-1){
				u+=((c[x]/er[i]%K)+(c[y]/er[i]%K)-(c[lca]/er[i]*2%K)+K)%K*er[i];
			}
			fod(i,m-1,0){
				if(B[i]){					 
					int v=(u/er[i]%K)/(B[i]/er[i]);
					u=add(u,cf(B[i],-v));
				}
			}
			printf("%lld\n",u);
		}
	}
	return 0;
}