#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],tmp[M];
    void exgcd(int* p,int* q,int x){
        if(!q[x])return;
        int d = p[x]/q[x];
        for(int i=x;i>=1;i--)p[i] = ((p[i]-1ll*q[i]*d)%k+k)%k;
        exgcd(q,p,x);
    }
    void ins(int n){
        fac(n,tmp);
        for(int i=m;i>=1;i--)if(tmp[i]){
            exgcd(a[i],tmp,i); 
            if(!a[i][i])for(int j=1;j<=m;j++)swap(a[i][j],tmp[j]);
        }
    }
    void qry(int w){
        fac(w,tmp); 
        //printf("qry %d\n",w);
        for(int i=m;i>=1;i--)if(a[i][i]){
            int g = __gcd(a[i][i],k),r = a[i][i]%g;
            int to = (tmp[i]+r)%g,d = 0;
            while((tmp[i]+1ll*d*a[i][i])%k != to)d++;
            for(int j=i;j>=1;j--)tmp[j] = (tmp[j]+1ll*a[i][j]*d)%k;
        }
        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);
            //printf("ins %d\n",v);
            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);
            //exit(0);
        }
    }

    return 0;
}