Little W owns a vast country. Initially, the country has only one city, numbered $1$. Little W intends to record the history of his country's transportation development. Specifically, Little W records $Q$ operations. Let $m$ be the maximum city number before each operation. Each operation is one of the following three types:

• 1 x v: Little W captures a new city and assigns it the number $m+1$. After the capture, Little W builds a new bidirectional road connecting $x$ and $m+1$ with weight $v$. ($1 \leq x \leq m$, $0 \leq v < V$)
• 2 x y v: Little W builds a new bidirectional road connecting $x$ and $y$ with weight $v$. ($1 \leq x \leq m$, $0 \leq v < V$)
• 3 x y: Little W asks for the minimum weight among all paths connecting $x$ and $y$. Here, a path may traverse a road multiple times. ($1 \leq x < y \leq m$)

Here, Little W defines the weight of a path as the $k$-ary XOR sum of the weights of all roads on the path. If a road is traversed $x$ times, it is also counted $x$ times when calculating the XOR sum. That is, traversing a road multiple times might result in a smaller path weight.

Note that there may be multiple roads connecting cities $x$ and $y$, and these roads may have the same or different weights.

Let the $k$-ary representation of $a$ be $a_1a_2\cdots a_m$ and the $k$-ary representation of $b$ be $b_1b_2\cdots b_n$. By padding with leading zeros such that $m = n$, their $k$-ary XOR sum is defined as the $k$-ary representation $(a_1+b_1)\bmod k(a_2 + b_2) \bmod k \cdots (a_n+b_n) \bmod k$.

Input

The first line contains three positive integers $Q$, $k$, and $m$. Here, we define $V=k^m$.

The next $Q$ lines each contain several numbers representing an operation.

Output

For each operation of type 3, output one integer per line representing the answer.

Examples

Input 1

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

Output 1

112852
113763
1001
1886

Subtasks

Subtask 1 ($2\%$): $Q \leq 30$, $V \leq 2\,000$.

Subtask 2 ($11\%$): $Q \leq 1\,000$, $V \leq 100\,000$.

Subtask 3 ($11\%$): No operation of type 2 exists.

Subtask 4 ($19\%$): $m = 1$.

Subtask 5 ($15\%$): $k = 2$.

Subtask 6 ($3\%$): $k$ is odd.

Subtask 7 ($39\%$): No special constraints.

For all test cases, $1 \leq Q \leq 2 \times 10^5$, $2 \le k$, $1 \leq m$, $V \leq 5 \times 10^7$.