#include <cstdio>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <queue>
typedef long long LL;
typedef unsigned long long ULL;
typedef std::pair<int, int> pii;
#define MP std::make_pair
#define fi first
#define se second
#define clr(f, n) memset(f, 0, (n) << 2)
#define cpy(f, g, n) memcpy(f, g, (n) << 2)
int read()
{
	int s = 0, f = 1;
	char c = getchar();
	while (!(c >= '0' && c <= '9'))
		f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c ^ 48), c = getchar();
	return f ? s : -s;
}
const int MAXN = 200005, MAXD = 30;
int Q, K, m, n = 1;
auto fplus = [](int x, int y){ return x + y >= K ? x + y - K : x + y; };
auto fminus = [](int x, int y){ return x >= y ? x - y : x + K - y; };
auto Fplus = [](int &x, int y){ return x = fplus(x, y); };
auto Fminus = [](int &x, int y){ return x = fminus(x, y); };
void swap(int a[], int b[], int n)
{
	for (int i = 0; i < n; i++)
		std::swap(a[i], b[i]);
}
int exgcd(int x, int y, LL &a, LL &b)
{
	if (!y) return a = 1, b = 0, x;
	int d = exgcd(y, x % y, b, a);
	b -= a * (x / y);
	return d;
}
int gcd(int x, int y)
{
	for (; y; std::swap(x, y)) x /= y;
	return x;
}
struct Linear_Base
{
	int p[MAXD][MAXD];
	void insert(int v[])
	{
		for (int i = m - 1; i >= 0; i--)
			if (v[i])
				while (v[i])
				{
					for (int j = 0; j <= i; j++)
						Fminus(p[i][j], (LL)(p[i][i] / v[i]) * v[j] % K);
					swap(p[i], v, i + 1);
				}
	}
	void query(int v[])
	{
		for (int i = m - 1; i >= 0; i--)
			if (v[i] && p[i][i])
			{
				int g = gcd(v[i], K);
				int c = (K - v[i] + g - 1) / g;
				LL a, b; exgcd(p[i][i], K, a, b);
				a = (K + c * a % K) % K;
				for (int j = 0; j <= i; j++)
					v[j] = (a * p[i][j] + v[j]) % K;
			}
	}
} lb;
int anc[MAXN][19], val[MAXN][MAXD], dep[MAXN];
int tmp[MAXD], tm[MAXD];
int getLca(int x, int y)
{
	if (dep[x] < dep[y]) std::swap(x, y);
	int dif = dep[x] - dep[y];
	for (int i = 0; i <= 18; i++, dif >>= 1)
		if (dif & 1) x = anc[x][i];
	if (x == y) return x;
	for (int i = 18; i >= 0; i--)
		if (anc[x][i] != anc[y][i])
			x = anc[x][i], y = anc[y][i];
	return anc[x][0];
}
void calc(int f[], int v)
{
	clr(f, m);
	for (int i = 0; v; v /= K, i++)
		f[i] = v % K;
}
void pplus(int f[], int g[])
{
	for (int i = 0; i < m; i++)
		Fplus(f[i], g[i]);
}
int calc(int f[])
{
	int v = 0;
	for (int i = 0, j = 1; i < m; i++, j *= K)
		v += f[i] * j;
	return v;
}
int main()
{
	Q = read(), K = read(), m = read();
	for (int _ = 1; _ <= Q; _++)
	{
		int o = read(), x = read(), y = read();
		if (o == 1)
		{
			anc[++n][0] = x, dep[n] = dep[x] + 1;
			for (int i = 1; i <= 18; i++)
				anc[n][i] = anc[anc[n][i - 1]][i - 1];
			calc(tmp, y), cpy(val[n], tmp, m), pplus(val[n], val[x]);
			for (int i = 0; i < m; i++) Fplus(tmp[i], tmp[i]);
			lb.insert(tmp);
		}
		else if (o == 2)
		{
			calc(tmp, read());
			for (int i = 0; i < m; i++) tm[i] = fplus(tmp[i], tmp[i]);
			lb.insert(tm);
			for (int i = 0; i < m; i++)
				Fplus(tmp[i], fplus(val[x][i], val[y][i]));
			lb.insert(tmp);
		}
		else
		{
			for (int i = 0; i < m; i++)
				tmp[i] = fplus(val[x][i], val[y][i]);
			lb.query(tmp);
			printf("%d\n", calc(tmp));
		}
	}
	return 0;
}