#include <bits/stdc++.h>
using namespace std;

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long

const int N = 2e5 + 5;

int q, k, m, n = 1;
int val[N], dep[N];
int f[N][18];
int base[30], mi[30];

int lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	fd(i, 17, 0) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	if(x == y) return x;
	fd(i, 17, 0) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

int add(int x, int y) {
	int res = 0;
	fo(i, 1, m) {
		res += mi[i - 1] * ((x + y) % k);
		x /= k, y /= k;
	}
	return res;
}

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

int mul(int x, int y) {
	int res = 0;
	fo(i, 1, m) {
		res += mi[i - 1] * ((ll)x % k * y % k);
		x /= k;
	}
	return res;
}

int getdt(int x, int y) {
	return x / mi[y] % k;
}

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;
	return;
}

int Inv(int x) {
	int a, b;
	exgcd(x, k, a, b);
	return (a + k) % k;
}

void ins(int x) {
	fd(i, m - 1, 0) {
		if(getdt(x, i)) {
			if(!base[i]) {
//				base[i] = mul(x, Inv(getdt(x, i)));
//				x = mul(x, k / __gcd(k, getdt(x, i)));
				base[i] = mul(x, Inv(getdt(x, i)));
				return;
			} else {
				int y = base[i];
				while(getdt(y, i)) {
					int u = getdt(x, i) / getdt(y, i);
					x = sub(x, mul(y, u));
					swap(x, y);
				}
				if(!getdt(y, i)) swap(x, y);
				base[i] = y;
			}
		}
	}
	return;
}

int query(int x) {
	fd(i, m - 1, 0) {
		if(!base[i]) continue;
		ins(mul(base[i], k / getdt(base[i], i)));
		if(!getdt(x, i)) continue;
		x = sub(x, mul(base[i], getdt(x, i) / getdt(base[i], i)));
	}
	return x;
}

int main() {
	scanf("%d %d %d", &q, &k, &m);
	mi[0] = 1;
	fo(i, 1, m) mi[i] = mi[i - 1] * k;
	fo(i, 1, q) {
		int ty; scanf("%d", &ty);
		if(ty == 1) {
			int x, v; scanf("%d %d", &x, &v);
			++n;
			val[n] = add(val[x], v);
			f[n][0] = x, dep[n] = dep[x] + 1;
			fo(j, 1, 17) f[n][j] = f[f[n][j - 1]][j - 1];
			ins(mul(v, 2));
		} else if(ty == 2) {
			int x, y, v; scanf("%d %d %d", &x, &y, &v);
			int z = lca(x, y);
			int num = sub(add(v, add(val[x], val[y])), mul(val[z], 2));
			ins(num);
		} else {
			int x, y; scanf("%d %d", &x, &y);
			int z = lca(x, y);
			int num = sub(add(val[x], val[y]), mul(val[z], 2));
			printf("%d\n", query(num));
		}
	}
	return 0;
}