Problem Description

Translated from JOI Open 2016 T1 "JOIRIS"

Problem Description

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

Initially, in the $i$-th column, there are blocks at $(i, 1), (i, 2), \ldots, (i, A_i)$.

Next, $10^4$ $1 \times K$ tiles will be dropped one by one, and the player needs to place each tile sequentially. Each tile is placed as follows:

The player first chooses whether to place the tile horizontally or vertically.
- If choosing vertically, the player also selects an integer $x$ ($1 \le x \le N$). The tile will drop onto the row above the topmost block in the $x$-th column. If there are no blocks in the $x$-th column, the tile will drop to the bottom of the well.
- If choosing horizontally, the player also selects an integer $x$ ($1 \le x \le N-K+1$). The tile will drop onto the row above the topmost block in the $x$-th to $x+K-1$-th columns. If there are no blocks in the $x$-th to $x+K-1$-th columns, the tile will drop to the bottom of the well.

After each tile stops falling, the system will check row by row from the bottom. If a row is completely filled with blocks, all blocks in that row will disappear, and all blocks above will move down by one grid.

The system then checks if 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 tile.

It is guaranteed that the bottom row is not completely filled with blocks at the start. Determine if the player can win and, if possible, output a strategy.

Input Format

The input consists of $N + 1$ lines.

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

Output Format

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

Otherwise, output $X+1$ lines, where $X$ represents the number of steps needed to clear 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 tile is placed vertically, output two integers, the first being $1$ and the second being $x$ (as described in the problem).
- If the $i$-th falling tile is placed horizontally, output two integers, the first being $2$ and the second being $x$ (as described in the problem).

Sample Input and Output

Sample Input #1

4 2
1
0
1
2

Sample Output #1

4
2 2
1 1
2 3
1 2

Sample Input #2

3 2
2
0
1

Sample Output #2

3
1 2
1 3
2 1

Sample Input #3

2 2
0
1

Sample Output #3

-1

Sample Input #4

5 3
1
0
1
0
1

Sample Output #4

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

Notes

Sample 1 Explanation

Data Constraints

This problem is group-tested.

For all data, $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.

见题面 Input 部分

见题面 Output 部分