小 W 拥有一个庞大的国家。这个国家初始的时候只有一座城池，编号为 $1$。小 W 打算记录他的国家交通发展的历程。具体的，小 W 记录了 $Q$ 次操作，记每一次操作前编号最大的城市为 $m$，每次操作是如下三种操作中的某一种：

• 1 x v。小 W 占领了一座新的城市并将其编号为 $m+1$。在攻占完成后小 W 新建了一条连接 $x$ 和 $m+1$ 的权值为 $v$ 的双向通行道路。($1 \leq x \leq m$，$0 \leq v < V$)
• 2 x y v。小 W 新建了一条连接 $x$ 和 $y$ 的权值为 $v$ 的双向通行道路。($1 \leq x \leq m$，$0 \leq v < V$)
• 3 x y。小 W 询问连接 $x$ 和 $y$ 的所有路径的权值中，最小的那一条路径的权值。这里一条路径可以重复经过一条道路多次。($1 ≤ x < y ≤ m$)

在这里，小 W 定义一条路径的权值为路径上所有道路权值的 $k$ 进制异或和。如果一条道路被经过了 $x$ 次，则在计算异或和的时候也会计算 $x$ 次。也就是说，有可能重复经过一条过路多次会使得路径权值变小。

注意城市 $x$、$y$ 之间可能会出现很多条连接它们的道路，这些道路权值可能相同，也可能不同。

设 $a$ 的 $k$ 进制表示为 $a_1a_2\cdots a_m$，$b$ 的 $k$ 进制表示为 $b_1b_2\cdots b_n$。，不妨在开头补零使得 $m = n$，则它们的 $k$ 进制异或和的 $k$ 进制表示为 $(a_1+b_1)\bmod k(a_2 + b_2) \bmod k \cdots (a_n+b_n) \bmod k$。

输入格式

第一行三个正整数，依次表示 $Q$，$k$，$m$。这里我们定义 $V=k^m$。

接下来 $Q$ 行，每行若干个数字，表示一次操作。

输出格式

对于每一次操作 $3$，输出一行一个整数表示答案。

样例数据

样例输入

10 2 20
1 1 114514
1 2 191981
1 2 1926
1 2 817
3 1 4
3 1 5
2 3 5 1949
2 1 4 1001
3 1 4
3 1 5

样例输出

112852
113763
1001
1886

子任务

Subtask 1（$2\%$）：$Q \leq 30$，$V \leq 2\,000$。

Subtask 2（$11\%$）：$Q \leq 1\,000$，$V \leq 100\,000$。

Subtask 3（$11\%$）：不存在操作 $2$。

Subtask 4（$19\%$）：$m = 1$。

Subtask 5（$15\%$）：$k = 2$。

Subtask 6（$3\%$）：$k$ 是奇数。

Subtask 7（$39\%$）：无特殊限制。

对于所有测试数据，满足 $1 \leq Q \leq 2 \times 10^5$，$2 \le k$，$1 \leq m$，$V \leq 5 \times 10^7$。