#include <cstdio>
#include <algorithm>

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 = 23;
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) {
  int z = 0;
  for(int i = 0; i < m; ++i) {
    int u = get(x, i);
    z += u * y % k * bit[i];
  }
  return z;
}

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]) {
          a[i] = x;
          break;
        }
        else {
          int v = get(a[i], i);
          int d = __gcd(u, v);
          x = red(mul(x, v / d), mul(a[i], u / d));
        }
      }
    }
  }
  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);
        int d = __gcd(u, v);
        x = red(mul(x, v / d), mul(a[i], u / d));
      }
    }
    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];
}

int 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]), w[z]);
      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]), w[z]);
      printf("%d\n",base.query(len));
    }
  }
  return 0;
}