#include<iostream>
#include<cstdio>
#define N 200000
#define M 26
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int gcd(int x,int y)
{
    if (!y) return x;
    return gcd(y,x%y);
}
int length,q,k,m,x,v;
long long sx,sy;
struct reads
{
    int d[M+1];
};
reads tmp,dp[N+1],c[M+1];
reads operator + (reads a,reads b)
{
    for (int i=0;i<=m-1;++i) a.d[i]=(a.d[i]+b.d[i])%k;
    return a;
}
reads operator * (reads a,int b)
{
    for (int i=0;i<=m-1;++i) a.d[i]=1ll*a.d[i]*b%k;
    return a;
}
reads F(int x)
{
    for (int i=0;i<=m-1;++i) tmp.d[i]=x%k,x/=k;
    return tmp;
}
int G(reads x)
{
    int res=0;
    for (int i=m-1;i>=0;--i) res=res*k+x.d[i];
    return res;
}
void exgcd(int x,int y)
{
    if (!y)
    {
	sx=1,sy=0;
	return;
    }
    exgcd(y,x%y);
    long long tx=sx;
    sx=sy,sy=tx-(x/y)*sy;
    return;
}
reads solve(int num,reads x)
{
    int ds=gcd(x.d[num],k);
    exgcd(x.d[num]/ds,k/ds),sx=(sx%k+k)%k;
    return x*sx;
}
reads get_gcd(int num,reads a,reads b,reads &c)
{
    a=solve(num,a),b=solve(num,b),exgcd(a.d[num],b.d[num]),sx=(sx%k+k)%k,sy=(sy%k+k)%k;
    if (!sx) c=b;
    else c=a;
    return a*sx+b*sy;
}
void Insert(reads x)
{
    int ds;
    reads y;
    for (int i=m-1;i>=0;--i)
	if (x.d[i])
	{
	    if (!c[i].d[i]) c[i]=x,ds=k/gcd(x.d[i],k),x=x*k;
	    else c[i]=get_gcd(i,c[i],x,y),ds=(k-y.d[i])/c[i].d[i],y=y+c[i]*ds;
	}
    return;
}
reads query(reads x)
{
    int ds,dst;
    reads y;
    for (int i=m-1;i>=0;--i)
	if (x.d[i]&&c[i].d[i])
	    y=solve(i,c[i]),ds=x.d[i]%y.d[i],dst=((ds-x.d[i])/y.d[i]+k)%k,x=x+y*dst;
    return x;
}
int main()
{
    int op,x,y,v;
    q=read(),k=read(),m=read();
    if (k&1)
    {
	while (q--)
	{
	    op=read();
	    if (op==1) x=read(),v=read();
	    else if (op==2) x=read(),y=read(),v=read();
	    else x=read(),y=read(),puts("0");
	}
	return 0;
    }
    length=1;
    while (q--)
    {
	op=read();
	if (op==1) x=read(),v=read(),dp[++length]=dp[x]+F(v),Insert(F(v)+F(v));
	else if (op==2) x=read(),y=read(),v=read(),Insert(dp[x]+dp[y]+F(v));
	else x=read(),y=read(),printf("%d\n",G(query(dp[x]+dp[y])));
    }
    return 0;
}