Background

Translated from JOI Open 2016 T1 "JOIRIS".

Problem Description

The play area of JOIRIS is called the "Well". It is a rectangular grid with width $N$ and sufficiently large height. The cell in the $i$-th column from the left and the $j$-th row from the bottom is denoted by $(i,j)$. During the game, each cell either contains a block or is empty.

At the beginning, in column $i$, and only in that column, the cells $(i,1), (i,2),\cdots, (i, A_i)$ contain blocks.

Next, $10^4$ dominoes of size $1 \times K$ fall one by one, and the player must place them in order. Each placement is performed as follows:

The player first chooses whether to place the domino horizontally or vertically.

• If the player chooses vertical placement, they must additionally choose an integer $x$ ($1 \le x \le N$). The domino will fall to the row just above the topmost block in column $x$. If there is no block in column $x$, the domino will fall to the bottom of the well.
• If the player chooses horizontal placement, they must additionally choose an integer $x$ ($1 \le x \le N-K+1$). The domino will fall to the row just above the highest topmost block among columns $x$ through $x+K-1$. If there are no blocks in columns $x$ through $x+K-1$, the domino will fall to the bottom of the well.

After each domino stops falling, the system checks the well row by row from the bottom upward. If a row is completely filled with blocks, all blocks in that row disappear, and all blocks above it move down by $1$ cell.

Then it checks whether there are any blocks left in the well. If there are no blocks, the game ends and the player wins. Otherwise, the player starts placing the next domino.

It is guaranteed that initially the bottom row is not completely filled with blocks. Determine whether the player can win. If it is possible, output one valid strategy.

Input Format

The input consists of $N + 1$ lines.

The first line contains two integers $N, K$.
In the next $N$ lines, the $i$-th line ($1 \le i \le N$) contains one integer $A_i$.

Output Format

If the player cannot win, output one line containing $-1$.

Otherwise, output $X+1$ lines, where $X$ is the number of moves needed to eliminate all blocks:

The first line contains an integer $X$. The next $i$-th line ($1 \le i \le X$) describes your strategy.

• If the $i$-th falling domino is placed vertically, output two integers. The first integer is $1$, and the second integer $x$ indicates the position where the player places the piece (as described above).
• If the $i$-th falling domino is placed horizontally, output two integers. The first integer is $2$, and the second integer $x$ indicates the position where the player places the piece (as described above).

4 2
1
0
1
2

4
2 2
1 1
2 3
1 2

3 2
2
0
1

3
1 2
1 3
2 1

2 2
0
1

-1

5 3
1
0
1
0
1

9
1 4
1 5
2 1
2 1
2 2
1 1
1 2
2 3
2 3

Hint

Explanation for Sample 1

Constraints and Notes

This problem uses bundled testdata.

For all testdata, $2\le N\le 50$, $1\le K\le N$, $0\le A_i \le 50$.

• Subtask 1 (15 points): $K=2$ and $N$ is odd.
• Subtask 2 (15 points): $K=2$ and $N$ is even.
• Subtask 3 (15 points): $K$ divides $N$.
• Subtask 4 (55 points): No additional constraints.

Translated by ChatGPT 5