#include<iostream>
#include<cstdio>
#include<cassert>
#define N 300000
#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],d1,d2;
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,reads b)
{
    for (int i=0;i<=m-1;++i) a.d[i]=(a.d[i]-b.d[i]+k)%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;
}
void get_gcd(int num,reads a,reads b)
{
    if (!b.d[num])
    {
	d1=a,d2=b;
	return;
    }
    get_gcd(num,b,a-b*(a.d[num]/b.d[num]));
    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;
}
void Insert(reads x)
{
    int ds;
    for (int i=m-1;i>=0;--i)
	if (x.d[i])
	{
	    if (!c[i].d[i]) x=solve(i,x),c[i]=x,ds=k/gcd(x.d[i],k),x=x*ds;
	    else get_gcd(i,c[i],x),c[i]=d1,x=d2;
	}
    return;
}
reads query(reads x)
{
    int ds,dst,p;
    for (int i=m-1;i>=0;--i)
	if (x.d[i]&&c[i].d[i])
	    p=gcd(c[i].d[i],k),ds=x.d[i]%p,dst=(ds-x.d[i]+k)%k,exgcd(c[i].d[i],k),sx=(sx*(dst/p)%k+k)%k,x=x+c[i]*sx;
    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;
}