There are $m$ binary variables on a plane, indexed $0, 1, \dots, m-1$. You do not know their initial values.

You can perform several types of operations:

Single-point flip, denoted as 1 x, which flips the binary variable with index $x$ (0 becomes 1, 1 becomes 0).

Single-controlled flip, denoted as 2 x y (where $x \neq y$), which flips the binary variable with index $y$ if the binary variable with index $x$ is 1 at the time of the operation; otherwise, it does nothing.

Double-controlled flip, denoted as 3 x y z (where $x, y, z$ are pairwise distinct), which flips the binary variable with index $z$ if both binary variables with indices $x$ and $y$ are 1 at the time of the operation; otherwise, it does nothing.

Given $n$ and $Q$, where $n$ is a non-negative integer less than $m$, you need to construct an operation sequence of length at most $Q$ such that for all possible initial values of these $m$ binary variables, the following conditions are satisfied:

If the initial values of the binary variables with indices $0, 1, \dots, n-1$ are all 1, then after executing the operation sequence, the binary variable with index $n$ is flipped, and all other variables remain the same as their initial values.

If the initial values of the binary variables with indices $0, 1, \dots, n-1$ are not all 1, then after executing the operation sequence, all variables remain the same as their initial values.

Note: It is impossible to check your constructed sequence against all $2^m$ possible cases. In the actual tests, for each test case, we will select a subset of possible initial configurations $T$, and you only need to ensure that your operation sequence satisfies the conditions for all configurations in $T$.

Input

The first line contains four positive integers $n, m, Q, case$. Here, $n, m, Q$ have the same meanings as described above, and $case$ is the identifier of the subtask. Specifically, if $case=0$, it indicates sample data.

Output

The first line contains an integer $k$, representing the length of your constructed operation sequence, where $0 \le k \le Q$.

The next $k$ lines each describe an operation. For the $i$-th line, first output an integer $ty \in \{1, 2, 3\}$ representing the operation type, followed by $ty$ integers representing the indices of the variables involved, formatted as described in the problem statement.

Examples

Input 1

3 5 25 0

Output 1

4
3 0 1 4
3 2 4 3
3 0 1 4
3 2 4 3

Note

You can verify the correctness of this solution by enumerating all initial configurations.

Constraints

Special Constraint A: For all $(x_0x_1\dots x_{m-1}) \in T$, it is guaranteed that $x_{n+1}=x_{n+2}=\dots=x_{m-1}=0$.

For all data, it is guaranteed that $0 \le n \le 100, m \ge n+2, Q \ge 8n+1$.