//Shirasu Azusa 2024.3
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=2e5+5;
int n,k,m,u=1,f[N][25],fa[N],d[N];

struct vec {
  int a[30],sz;
  vec(int sz=29) {rep(i,0,sz) a[i]=0;}
} s[N],t[N][20],a[N],b[30];
vec operator ^ (const vec a,const vec b) {
  vec c(m);
  rep(i,0,m-1) c.a[i]=(a.a[i]+b.a[i])%k;
  return c;
}
vec operator * (const vec a,const int x) {
  vec c(m);
  rep(i,0,m-1) c.a[i]=a.a[i]*x%k;
  return c;
}
vec getvec (int x) {
  vec c(m);
  rep(i,0,m-1) c.a[i]=x%k, x/=k;
  return c;
}
ll getval (const vec a) {
  ll res=0;
  per(i,m-1,0) res=res*k+a.a[i];
  return res;
}
void work (int i,vec &a,vec &b) {
  if(!b.a[i]) return;
  int p=a.a[i]/b.a[i];
  rep(j,0,m-1) a.a[j]=a.a[j]-p*b.a[j];
  rep(j,0,m-1) a.a[j]=(a.a[j]%k+k)%k;
  work(i,b,a);
}
pii exgcd(int a,int b) {
  if(b==0) {return pii(1,0);}
  auto [x,y]=exgcd(b,a%b);
  return pii(y,x-a/b*y);
}
void ins_inner (vec x) {   
  per(i,m-1,0) if(x.a[i]) {
    if(!b[i].a[i]) {
      int g=__gcd(x.a[i],k);
      auto [p,q]=exgcd(x.a[i]/g,k/g);
      p=(p%k+k)%k;
      rep(j,0,m-1) x.a[j]=x.a[j]*p%k;
      b[i]=x; return;
    }
    work(i,b[i],x);
    if(!b[i].a[i]) swap(x,b[i]);
  }
}
void ins (vec x) {
  per(i,m-1,0) if(x.a[i]) {
    ins_inner(x);
    int g=k/__gcd(k,x.a[i]);
    x=x*g;
  }
}
vec getpath (int u,int v) {
  vec c(m); if(d[u]<d[v]) swap(u,v);
  per(h,18,0) if(d[f[u][h]]>=d[v])
    c=c^t[u][h], u=f[u][h];
  per(h,18,0) if(f[u][h]!=f[v][h])
    c=c^t[u][h]^t[v][h], u=f[u][h], v=f[v][h];
  if(u!=v) c=c^t[u][0]^t[v][0];
  return c;
}
vec qry (vec x) {
  //cout<<"VEC: ";
  //per(i,m-1,0) cout<<x.a[i]; puts("");
  per(i,m-1,0) if(b[i].a[i]&&x.a[i]) {
    vec y=b[i];
    int g=__gcd(y.a[i],k); assert(y.a[i]==g); // // // // //
    int p=x.a[i]/y.a[i];
    rep(j,0,m-1) x.a[j]=x.a[j]-y.a[j]*p;
    rep(j,0,m-1) x.a[j]=(x.a[j]%k+k)%k;
  }
  return x;
}

signed main() {
  n=read(), k=read(), m=read(); d[1]=1;
  rep(i,1,n) {
    int opt=read();
    if(opt==1) {
      ++u; fa[u]=read(); a[u]=getvec(read());
      //per(j,m-1,0) cout<<a[u].a[j]; puts("");
      if(k&1) ins(a[u]);
      else ins(a[u]*2);
      s[u]=s[fa[u]]^a[u], t[u][0]=a[u];
      d[u]=d[fa[u]]+1, f[u][0]=fa[u];
      rep(h,1,18) f[u][h]=f[f[u][h-1]][h-1];
      rep(h,1,18) t[u][h]=t[u][h-1]^t[f[u][h-1]][h-1];
    } else if(opt==2) {
      int u=read(), v=read(); vec w=getvec(read());
      if(k&1) ins(w);
      else ins(w*2);
      vec pth=getpath(u,v); w=w^pth; ins(w);
    } else {
      int u=read(), v=read(); vec pth=getpath(u,v);
      vec res=qry(pth); printf("%lld\n",getval(res));
    }
    //cout<<"LINEAR BASIS:\n";
    //per(i,m-1,0) {
    //  per(j,m-1,0) cout<<b[i].a[j]; puts("");
    //}
  }
  return 0;
}