#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+10,M = 30;
int q,k,m,n;

int dep[MAXN],dis[MAXN],fa[20][MAXN];

namespace Num{
    int p[M],q[M];
    void fac(int n,int* p){ for(int x=1;x<=m;x++)p[x]=n%k,n/=k;}
    int rfac(int* p){int num = 0; for(int i=M;i>=1;i--)num = num*k + p[i]; return num; }
    int add(int a,int b){
        fac(a,p); fac(b,q); 
        for(int i=1;i<=m;i++)p[i] = (p[i]+q[i])%k;
        return rfac(p);
    }
    int mul(int a,int b){
        fac(a,p);
        for(int i=1;i<=m;i++)p[i] = 1ll*p[i]*b%k;
        return rfac(p);
    }
    //
    int a[M][M],b[M][M],tmp[M],cur[M];
    void exgcd(int* p,int* q,int x){
        if(!q[x])return;
        int d = p[x]/q[x];
        if(d)for(int i=x;i>=1;i--)p[i] = ((p[i]-1ll*q[i]*d)%k+k)%k;
        exgcd(q,p,x);
    }
    void F(int* p,int* q,int x){
        exgcd(p,q,x);
        if(!p[x])for(int j=1;j<=x;j++)swap(p[j],q[j]);
    }
    void ins(int n){
        fac(n,tmp); 
        for(int i=m;i>=1;i--)if(tmp[i])F(a[i],tmp,i);
    }
    void ins(int* tmp){
        for(int i=m;i>=1;i--)if(tmp[i])F(a[i],tmp,i);
    }
    void _exgcd(int a,int b,int& x,int& y){
        if(!b)return x=1,y=0,void();
        _exgcd(b,a%b,x,y);
        int x0 = x,y0 = y;
        x = y0; y = x0 - (a/b)*y0;
    }
    void qry(int w){
        fac(w,tmp); memcpy(b,a,sizeof b);
        for(int i=m;i>=1;i--)if(a[i][i]){
            int g = __gcd(a[i][i],k);
            int to = tmp[i]%g,d = 0,dd = 0;
            _exgcd(a[i][i],k,d,dd);
            d *= (to-tmp[i]) / g; d = (d%k+k)%k;
            for(int j=i;j>=1;j--)tmp[j] = (tmp[j]+1ll*a[i][j]*d)%k;
            //将基底的k/g倍插入
            memset(cur,0,sizeof cur);
            for(int j=1;j<i;j++)cur[j] = 1ll*a[i][j] * (k/g)%k;
            ins(cur);
        }
        memcpy(a,b,sizeof a);
        w = rfac(tmp); cout<<w<<"\n";
    }
}; using Num::add; using Num::mul; using Num::ins; using Num::qry;

int lca(int x,int y){
    if(dep[x] < dep[y])swap(x,y);
    for(int j=19;j--;)if(dep[x]-(1<<j) >= dep[y])x = fa[j][x];
    if(x==y)return x;
    for(int j=19;j--;)if(fa[j][x] != fa[j][y])x = fa[j][x],y = fa[j][y];
    return fa[0][x];
}

int W(int x,int y){
    int p = lca(x,y); 
    return add(add(dis[x],dis[y]),mul(dis[p],2*(k-1)));
}

int main(){
    freopen("city.in","r",stdin); freopen("city.out","w",stdout);
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>q>>k>>m; n = 1;

    for(int o,x,y,v;q--;){
        cin>>o;
        if(o==1){
            cin>>x>>v;
            n++; dis[n] = add(dis[x],v),dep[n] = dep[x] + 1,fa[0][n] = x;
            for(int j=1;j<20;j++)fa[j][n] = fa[j-1][fa[j-1][n]];

            v = mul(v,2);
            ins(v);
        }else if(o==2){
            cin>>x>>y>>v;
            int w = add(W(x,y),v); 
            
            ins(w);
        }else{
            cin>>x>>y;

            int w = W(x,y); 
            qry(w);
        }
    }

    return 0;
}