#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int w=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) w=w*10+ch-'0',ch=getchar();
	return w;
}
int q,k,m,cnt=1;
int st[25][200005],ts[25][200005],s[200005],dep[200005];
int vis[30],b[30];
void init(){
	b[0]=1;
	for(int i=1;i<=m+1;i++) b[i]=b[i-1]*k;
}
int findbit(int x,int nb){
	return x/b[nb]%k;
}
void insert(int x){
	// printf("insert:: %d\n",x);
	for(int i=m-1;i>=0;i--){
		if(findbit(x,i)==0) continue;
		if(!vis[i]) return vis[i]=x,void();
		while(findbit(vis[i],i)&&findbit(x,i)){
			if(vis[i]>=x){
				int p=findbit(vis[i],i)/findbit(x,i);
				for(int j=i;j>=0;j--){
					int nbit=findbit(vis[i],j);
					vis[i]-=nbit*b[j];
					nbit=(nbit+k-p*findbit(x,j)%k)%k;
					vis[i]+=nbit*b[j];
				}
			}else swap(vis[i],x);
		}
		if(vis[i]<x) swap(vis[i],x);
	}
}
int query(int x){
	int sum=0;
	for(int i=m-1;i>=0;i--){
		if(findbit(x,i)==0) continue;
		if(!vis[i]){sum+=findbit(x,i)*b[i];x%=b[i];continue;}
		int nw=vis[i];
		while(findbit(nw,i)&&findbit(x,i)){
			if(nw>=x){
				int p=findbit(nw,i)/findbit(x,i);
				// printf("%d %d\n",nw,x);
				for(int j=i;j>=0;j--){
					int nbit=findbit(nw,j);
					nw-=nbit*b[j];
					nbit=(nbit+k-p*findbit(x,j)%k)%k;
					nw+=nbit*b[j];
				}
				// printf("%d %d\n",nw,x);
			}else swap(nw,x);
		}
		swap(nw,x);
	}
	return sum;
}
int kxor(int x,int y){
	int sum=0;
	for(int i=m-1;i>=0;i--){
		int nbit=findbit(x,i)+findbit(y,i);
		nbit%=k;
		sum+=b[i]*nbit;
	}
	return sum;
}
int lca(int u,int v){
	int nw=0;
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=18;i>=0;i--){
		if(dep[st[i][u]]>=dep[v]){
			nw=kxor(nw,ts[i][u]);
			u=st[i][u];
		}
	}
	if(u==v) return nw;
	for(int i=18;i>=0;i--){
		if(st[i][u]!=st[i][v]){
			nw=kxor(kxor(ts[i][u],ts[i][v]),nw);
			u=st[i][u],v=st[i][v];
		}
	}
	nw=kxor(nw,kxor(ts[0][u],ts[0][v]));
	return nw;
}
main(){
	q=read(),k=read(),m=read();
	init();dep[1]=1;
	while(q--){
		int op=read(),x=read(),y=read();
		if(op==1){
			cnt++;
			st[0][cnt]=x;ts[0][cnt]=y;
			dep[cnt]=dep[x]+1;
			for(int i=1;st[i-1][cnt];i++){
				st[i][cnt]=st[i-1][st[i-1][cnt]];
				ts[i][cnt]=kxor(ts[i-1][st[i-1][cnt]],ts[i-1][cnt]);
				// printf("%d %d\n",i,ts[i][cnt]);
			}
			insert(kxor(y,y));
			s[cnt]=kxor(s[x],y);
		}else if(op==2){
			int v=read();
			insert(kxor(kxor(s[x],s[y]),v));
		}else{
			int p=lca(x,y);
			// printf("%lld\n",p);
			printf("%lld\n",query(p));
		}
		// puts("QWQ");
		// for(int i=m-1;i>=0;i--) printf("%d ",vis[i]);
		// puts("");
		// for(int i=1;i<=cnt;i++) printf("%d ",s[i]);puts("");
		// for(int i=1;i<=cnt;i++) printf("%d ",ts[0][i]);puts("");
		// puts("END");
		// puts("");
	}
}