#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;

namespace IO {
  #define isdigit(x) (x >= '0' && x <= '9')
  template<typename T>
  inline void read(T &x) {
    x = 0; char ch = getchar(); int f = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    if(f) x = -x;
  }
  template<typename T>
  inline void write(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
  }
  #undef isdigit
}
using namespace IO;

const int N = 2e5 + 10;
const int M = 25;
int Q, k, m;

int bit[M];
inline int get(int x, int p) {
  return x / bit[p] % k;
}

inline int add(int x, int y) {
  int z = 0;
  for(int i = 0; i < m; ++i) {
    int u = get(x, i), v = get(y, i);
    if((u += v) >= k) u -= k;
    z += u * bit[i];
  }
  return z;
}

inline int red(int x, int y) {
  int z = 0;
  for(int i = 0; i < m; ++i) {
    int u = get(x, i), v = get(y, i);
    if((u -= v) < 0) u += k;
    z += u * bit[i];
  }
  return z;
}

inline int mul(int x, int y) {
  y %= k;
  if(y < 0) y += k;
  int z = 0;
  for(int i = 0; i < m; ++i) {
    int u = get(x, i);
    u = u * y % k;
    z += u * bit[i];
  }
  return z;
}

inline void out(int x) {
  for(int i = m - 1; ~i; --i)
    printf("%d",get(x,i));
  puts("");
}

void exgcd(int a, int b, int &x, int &y) {
  if(b == 0) x = 1, y = 0;
  else exgcd(b, a % b, y, x), y -= a / b * x;
}

int kgcd(int x, int y, int p) {
  int u = get(x, p), v = get(y, p);
  if(v == 0) return x;
  else return kgcd(y, red(x, mul(y, u / v)), p);
}

struct LinearBase {
  int a[M];

  inline void insert(int x) {
    for(int i = m - 1; ~i; --i) {
      int u = get(x, i);
      if(u) {
        if(!a[i]) {
          int t1 = 0, t2 = 0;
          exgcd(u, k, t1, t2);
          a[i] = mul(x, t1); 
          x = mul(x, k / __gcd(k, u));
        }
        else {
          if(u % get(a[i], i)) a[i] = kgcd(a[i], x, i);
          x = red(x, mul(a[i], u / get(a[i], i)));
        }
      }
    }
  }

  inline int query(int x) {
    for(int i = m - 1; ~i; --i) {
      int u = get(x, i);
      if(u && a[i]) {
        int v = get(a[i], i);
        x = red(x, mul(a[i], u / v));
      }
    }
    return x;
  }
}base;

void init() {
  bit[0] = 1;
  for(int i = 1; i <= m - 1; ++i)
    bit[i] = bit[i - 1] * k;
}

int dep[N], w[N];
int fa[N][18];

inline int lca(int x, int y) {
  if(dep[x] < dep[y]) swap(x, y);
  for(int i = 17; ~i; --i)
    if(dep[fa[x][i]] >= dep[y])
      x = fa[x][i];
  if(x == y) return x;
  for(int i = 17; ~i; --i)
    if(fa[x][i] ^ fa[y][i])
      x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}

signed main() {
  read(Q), read(k), read(m);
  init();
  int tot = 1;
  for(int i = 1, op, x, y, v; i <= Q; ++i) {
    read(op);
    if(op == 1) {
      read(x), read(v);
      fa[++tot][0] = x;
      for(int i = 1; i <= 17; ++i)
        fa[tot][i] = fa[fa[tot][i - 1]][i - 1];
      dep[tot] = dep[x] + 1;
      w[tot] = add(w[x], v);
      base.insert(mul(v, 2));
    } 
    else if(op == 2) {
      read(x), read(y), read(v);
      int z = lca(x, y);
      int len = red(add(w[x], w[y]), mul(w[z], 2));
      len = add(len, v);
      base.insert(len);
    } 
    else {
      read(x), read(y);
      int z = lca(x, y);
      int len = red(add(w[x], w[y]), mul(w[z], 2));
      printf("%d\n",base.query(len));
    }
  }
  return 0;
}