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

template<typename Tp>
IN void read(Tp &x) {
    x = 0; char ch = getchar(); int f = 0;
    for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());
    for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
    if (f) x = ~x + 1;
}

const int LG = 17, N = 2e5 + 5;
int fa[N][LG + 2], dep[N];

IN int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for(int i = LG; ~i; i--) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for(int i = LG; ~i; i--) if (fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

namespace K_Base {
    int bit[25], K, m, val[N];
    IN void init(){bit[0] = 1; for(int i = 1; i <= m; i++) bit[i] = bit[i - 1] * K;}
    IN int getbit(int x, int p){return x / bit[p] % K;}
    
    IN int add(int x, int y) {
        int z = 0;
        for(int i = 0, u; i < m; i++) {
            u = getbit(x, i); if ((u += getbit(y, i)) >= K) u -= K; z += u * bit[i];
        }
        return z;
    }
    IN int reduce(int x, int y) {
        int z = 0;
        for(int i = 0, u; i < m; i++) {
            u = getbit(x, i); if ((u -= getbit(y, i)) < 0) u += K; z += u * bit[i];
        }
        return z;
    }
    IN int mul(int x, int y) {
        y %= K; if (y < 0) y += K; int z = 0;
        for(int i = 0; i < m; i++) z += getbit(x, i) * y % K * bit[i];
        return z;
    }
    IN int exgcd(int a, int b, int &x, int &y) {
        if (!b) return x = 1, y = 0, a;
        int d = exgcd(b, a % b, y, x); y -= a / b * x; return d;
    }
    
    struct LinearBase {
        int p[25];
        IN void insert(int x) {
            for(int i = m - 1; ~i; i--) if (getbit(x, i)) {
                if (!p[i]) {
                    int t1 = 0, t2 = 0, d = exgcd(getbit(x, i), K, t1, t2);
                    p[i] = mul(x, t1), x = mul(x, K / d);
                }
                for(; getbit(x, i); p[i] = reduce(p[i], mul(x, getbit(p[i], i) / getbit(x, i))), swap(p[i], x));
            }
        }
        IN int query(int x) {
            for(int i = m - 1; ~i; i--) {
                int u = getbit(x, i);
                if (u && p[i]) x = reduce(x, mul(p[i], u / getbit(p[i], i)));
            }
            return x;
        }
    }bs;
   
    IN int getVal(int x, int y){return reduce(add(val[x], val[y]), mul(val[LCA(x, y)], 2));}
}
using namespace K_Base;

int main() {
    int q, cnt = 1; read(q), read(K), read(m), init();
    for(int op, x, y, v, z; q; --q) {
        read(op);
        if (op == 1) {
            read(x), read(v), fa[++cnt][0] = x, val[cnt] = add(val[x], v), dep[cnt] = dep[x] + 1;
            for(int i = 1; i <= LG; i++)
                if (!fa[cnt][i - 1]) fa[cnt][i] = fa[fa[cnt][i - 1]][i - 1]; else break;
            bs.insert(mul(val[cnt], 2));
        }
        else if (op == 2) read(x), read(y), read(v), bs.insert(add(v, getVal(x, y)));
        else read(x), read(y), printf("%d\n", bs.query(getVal(x, y)));
    }
}