#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
int quickPower(int x,int y)
{
    int res=1;
    while (y){
        if (y&1) res=res*x;
        x=x*x;
        y>>=1;
    }
    return res;
}
void BellaKira()
{
    int Q,K,m;
    cin>>Q>>K>>m;
    int V=quickPower(K,m);
    vector<int>gd(V+1,0);
    for (int i=1;i<=V;i++) gd[i]=__gcd(i,V);
    vector<poly>fa(Q+1,poly(20,0)),dis(Q+1,poly(30,0));
    vector<poly>basis(30,poly());
    vector<int>dep(Q+1,0);
    dep[1]=1;
    int n=1;
    function<poly(poly,poly)>add=[&](poly x,poly y)
    {
        for(int i=0;i<30;i++) x[i]=(x[i]+y[i])%K;
        return x;
    };
    function<poly(poly,int)>mul=[&](poly x,int y)
    {
        for(int i=0;i<30;i++) x[i]=(x[i]*y)%K;
        return x;
    };
    function<poly(poly,poly)>del=[&](poly x,poly y)
    {
        for(int i=0;i<30;i++) x[i]=(x[i]-y[i]+K)%K;
        return x;
    };
    function<poly(int)>trans=[&](int x)
    {
        poly res;
        for (int i=0;i<30;i++) res.push_back(x%K),x/=K;
        return res;
    };
    function<void(poly&,poly&,int)>work=[&](poly &x,poly &y,int i)
    {
        while (y[i]!=0)
        {
            if (x[i]<y[i]) swap(x,y);
            int t=x[i]/y[i];
            for (int j=0;j<30;j++)
                x[j]=(x[j]-t*y[j]+K)%K;
        }
    };
    function<void(poly)>ins=[&](poly x)
    {
        for (int i=29;i>=0;i--)
            if (x[i])
            {
                if (basis[i].empty())
                {
                    basis[i]=x;
                    // cout<<"!!!!"<<i<<endl;
                    return;
                } else
                {
                    work(basis[i],x,i);
                }
            }
    };

    function<poly(poly)>qry=[&](poly x)
    {
        for (int i=29;i>=0;i--)
            if (x[i])
            {
                if (!basis[i].size()) continue;
                x=del(x,mul(basis[i],(x[i]/basis[i][i])));
            }
        return x;
    };
    function<int(int,int)>lca=[&](int x,int y)
    {
        // cout<<x<<","<<y<<endl;
        if (dep[x]<dep[y]) swap(x,y);
        // cout<<x<<","<<y<<endl;
        for (int i=18;i>=0;i--)
            if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
        // cout<<x<<","<<y<<endl;
        if (x==y) return x;
        for (int i=18;i>=0;i--) 
            if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    };
    while (Q--)
    {
        int opt,x,y;
        cin>>opt>>x>>y;
        // cout<<"!!"<<opt<<" "<<x<<" "<<y<<endl;
        if (opt==1)
        {
            poly v=trans(y);
            // for (auto u:v) cout<<u<<",";
            // cout<<endl;
            n++;
            dep[n]=dep[x]+1;
            fa[n][0]=x;
            for (int i=1;i<=18;i++)
                fa[n][i]=fa[fa[n][i-1]][i-1];
            // cout<<"!!"<<endl;
            dis[n]=add(dis[x],v);
            // cout<<"!!"<<endl;
            ins(add(v,v));
        }
        else
        if (opt==2)
        {
            int w;
            cin>>w;
            poly v=trans(w);
            int z=lca(x,y);
            ins(add(v,v));
            v=add(v,dis[x]);
            v=add(v,dis[y]);
            v=del(v,dis[z]);
            v=del(v,dis[z]);
            ins(v);
        }
        else 
        if (opt==3)
        {
            int z=lca(x,y);
            // cout<<x<<","<<y<<" "<<z<<endl;
            poly v=del(add(dis[x],dis[y]),dis[z]);
            v=del(v,dis[z]);
            // for (auto u:v) cout<<u<<",";
            // cout<<endl;
            poly now=qry(v);
            reverse(now.begin(),now.end());
            int ans=0;
            for (auto u:now) ans=ans*K+u;
            cout<<ans<<'\n';
        }
        // for (int i=29;i>=0;i--)
        // {
        //     if (basis[i].size())
        //     {
        //         for (int j=29;j>=0;j--) cout<<basis[i][j]<<" ";
        //         cout<<endl;
        //     }
        // }
        // cout<<endl;
    }
}
signed main()
{
    // freopen("A.in","r",stdin);
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}