#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,Q,k,m;
int opt[200005],_x[200005],_y[200005],_w[200005];

int cnt;
int head[200005];
struct eg{
	int to,nxt,w;
}edge[200005];

void make(int u,int v,int w){
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

int mo(int x){
	x %= k;
	if(x < 0) x += k;
	return x;
}
ll P[35];
int add(int x,int y){
	int res = 0;
	rep(i,0,m - 1){
		res += P[i] * mo(x + y);
		x /= k;y /= k;
	}
	return res;
}

int sub(int x,int y){
	int res = 0;
	rep(i,0,m - 1){
		res += P[i] * mo(x - y);
		x /= k;y /= k;
	}
	return res;
}

int sum[200005],fa[200005],dep[200005],dfn[200005];	
int ST[20][200005];
void dfs(int u){
	dep[u] = dep[fa[u]] + 1;
	dfn[u] = ++cnt;
	for(int i = head[u];i;i = edge[i].nxt){
		int v = edge[i].to;
		sum[v] = add(sum[u],edge[i].w);
		dfs(v);
	}
}

inline int cmp(int x,int y){
	if(dep[x] < dep[y]) return x;
	return y;
}

inline int qry(int l,int r){
	int x = __lg(r - l + 1);
	return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}

inline int LCA(int u,int v){
	if(u == v) return u;
	u = dfn[u];v = dfn[v];
	if(u > v) swap(u,v);
	return fa[qry(u + 1,v)];
}

int getdis(int u,int v){
	int d = LCA(u,v);
	return sub(sub(add(sum[u],sum[v]),sum[d]),sum[d]);
}

ll w[35][35];
int exgcd(int a,int b,int &x0,int &y0){
	if(!b){
		x0 = 1;
		y0 = 0;
		return a;
	}
	int x1,y1;
	int d = exgcd(b,a % b,x1,y1);
	x0 = y1;
	y0 = x1 - (a / b) * y1;
	return d;
}

void insert(int val){
//	printf("insert %d\n",val);
	ll cur[35];
	rep(i,0,m - 1){
		cur[i] = val % k;
		val /= k;
	}
	reverse(cur,cur + m);	
/*	rep(i,0,m - 1) printf("%lld ",cur[i]);
	printf("\n");
	printf("martix w:\n");
	rep(i,0,m - 1){
		rep(j,0,m - 1) printf("%lld ",w[i][j]);
		printf("\n");
	}
	printf("fin\n");*/

	int p,q;
	ll r,temp;
	rep(i,0,m - 1){
		if(!cur[i]) continue;

		if(!w[i][i] || cur[i] % w[i][i]){//击败事件
			if(w[i][i]) exgcd(cur[i],w[i][i],p,q);
			else exgcd(cur[i],k,p,q);

			rep(j,0,m - 1){
				cur[j] = (p * cur[j] + q * w[i][j]) % k;
				if(cur[j] < 0) cur[j] += k;
			}

			rep(j,0,m - 1) swap(cur[j],w[i][j]);
			r = k / w[i][i];
			temp = 0;
			rep(j,0,m - 1) temp += (r * w[i][j] % k) * P[m - j - 1];
			insert(temp);
		}
		assert(w[i][i]);
		r = cur[i] / w[i][i];
		rep(j,0,m - 1){
			cur[j] = (cur[j] - r * w[i][j]) % k;
			if(cur[j] < 0) cur[j] += k;
		}
	}
//	printf("fin\n");
}

int query(int val){
//	printf("query %d\n",val);
	ll cur[35];
	rep(i,0,m - 1){
		cur[i] = val % k;
		val /= k;
	}
	reverse(cur,cur + m);
//	rep(i,0,m - 1) printf("%lld ",cur[i]);
//	printf("\n");

/*	rep(i,0,m - 1){
		rep(j,0,m - 1) printf("%lld ",w[i][j]);
		printf("\n");
	}
	printf("\n");*/
	rep(i,0,m - 1){
		if(!w[i][i]) continue;
		ll r = cur[i] / w[i][i];
		rep(j,0,m - 1){
			cur[j] = (cur[j] - r * w[i][j]) % k;
			if(cur[j] < 0) cur[j] += k;
		}
//		printf("pos %d\n",i);
//		rep(j,0,m - 1) printf("%lld ",cur[j]);
//		printf("\n");
	}
	reverse(cur,cur + m);
	ll res = 0;
	rep(i,0,m - 1) res += cur[i] * P[i];
//	printf("%lld\n",res);
	return res;
}

int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d%d",&Q,&k,&m);
	P[0] = 1;
	rep(i,1,m - 1) P[i] = P[i - 1] * k;
	n = 1;
	int _q = 1;
	rep(i,1,Q){
		scanf("%d%d",&opt[_q],&_x[_q]);
		if(opt[_q] == 1){
			scanf("%d",&_w[_q]);
			++n;
			fa[n] = _x[_q];
			make(_x[_q],n,_w[_q]);
		}else{
			scanf("%d",&_y[_q]);
			if(opt[_q] == 2) scanf("%d",&_w[_q]);			
		}
		_q++;
	}
	Q = _q - 1;
//	rep(i,1,Q) printf("%d %d %d %d\n",opt[i],_x[i],_y[i],_w[i]);
	cnt = 0;
	dfs(1);
	rep(i,1,17){
		rep(j,1,n){
			if(j + (1 << i) - 1 > n) break;
			ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]);
		}
	}

	rep(i,1,Q){
		if(opt[i] == 1){
			insert(add(_w[i],_w[i]));		
		}else if(opt[i] == 2){
			insert(add(getdis(_x[i],_y[i]),_w[i]));
		}else{
			printf("%d\n",query(getdis(_x[i],_y[i])));
		}
	}
	return 0;
}