#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=2e5+9;
ll Q,k,m,n=1,fa[20][N],dep[N];
struct Int{
    ll a[32];
    void clear(){memset(a,0,sizeof(a));}
    ll val(){
        ll v=0;
        per(i,m-1,0)v=v*k+a[i];
        return v;
    }
}D[32],dis[N];
Int operator+(const Int&a,const Int&b){
    Int c;c.clear();
    rep(i,0,m-1)c.a[i]=(a.a[i]+b.a[i])%k;
    return c;
}
Int operator-(const Int&a,const Int&b){
    Int c;c.clear();
    rep(i,0,m-1)c.a[i]=(a.a[i]-b.a[i]+k)%k;
    return c;
}
Int operator*(const Int&a,const ll&b){
    Int c;c.clear();
    rep(i,0,m-1)c.a[i]=a.a[i]*b%k;
    return c;
}
void exgcd(ll a,ll b,ll&x,ll&y){
    if(!b)return x=1,y=0,void();
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
Int Make(ll x){
    Int a;a.clear();
    rep(i,0,m-1)a.a[i]=x%k,x/=k;
    return a;
}
ll Inv(ll a){
    ll x=0,y=0;
    exgcd(a,k,x,y);
    return (x%k+k)%k;
}
void Insert(Int a){
    per(i,m-1,0){
        if(!a.a[i])continue;
        if(!D[i].a[i])D[i]=a*Inv(a.a[i]),a=a*(k/__gcd(k,a.a[i]));
        while(a.a[i]){
            D[i]=D[i]-a*(D[i].a[i]/a.a[i]);
            swap(a,D[i]);
        }
    }
}
Int Query(Int x){
    per(i,m-1,0){
        if(!D[i].a[i])continue;
        x=x-D[i]*(x.a[i]/D[i].a[i]);
    }
    return x;
}
ll LCA(ll x,ll y){
    if(dep[x]<dep[y])swap(x,y);
    ll d=dep[x]-dep[y];
    per(i,18,0){
        if((d>>i)&1)x=fa[i][x];
    }
    per(i,18,0){
        if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
    }
    if(x==y)return x;
    return fa[0][x];
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    Q=read(),k=read(),m=read();
    while(Q--){
        ll op=read(),x=read(),y=read();
        if(op==1){
            Int q=Make(y);
            n++;
            dis[n]=dis[x]+q;
            Insert(q+q);
            fa[0][n]=x,dep[n]=dep[x]+1;
            rep(i,1,18)fa[i][n]=fa[i-1][fa[i-1][n]];
        }
        else if(op==2){
            ll w=read(),lca=LCA(x,y);
            Int q=Make(w);
            Int d=dis[x]+dis[y]+q;
            Insert(d),Insert(q+q);
        }
        else {
            Int q=dis[x]+dis[y],res=Query(q);
            write(res.val()),putchar('\n');
        }
    }
    return 0;
}