P9195 [JOI Open 2016] JOIRIS

**译自 [JOI Open 2016](https://contests.ioi-jp.org/open-2016/index.html) T1 「JOIRIS」**

JOIRIS 的游戏区域名叫「井」，是一个宽度为 $N$，高度足够大的矩形网格。位于左数第 $i$ 列，从下往上数第 $j$ 列的格子记作 $(i,j)$。游戏过程中，每个格子要不有一个方块，要不没有方块。 开始时，在第 $i$ 列有且仅有 $(i,1), (i,2),\cdots, (i, A_i)$ 有方块。 接下来，$10^4$ 个 $1 \times K$ 的骨牌一个个下落，玩家要依次放置骨牌。每次放置骨牌按照如下方式进行： 玩家先选择骨牌是横向放置还是纵向放置。 - 若选择纵向，玩家还需再选择一个整数 $x$（$1 \le x \le N$）。一个骨牌会下落到第 $x$ 列最上方方块的上面一行。若第 $x$ 列没有方块，骨牌会下落到井底。 - 若选择横向，玩家还需再选择一个整数 $x$（$1 \le x \le N-K+1$）。一个骨牌会下落到第 $x$ 列至第 $x+K-1$ 列最上方方块的上面一行。若第 $x$ 列至第 $x+K-1$ 列没有方块，骨牌会下落到井底。 每个骨牌停止下落后，系统将从井底往上逐行检查，如果有一行格子被方块填满，该行的所有方块都会消失，且上方的所有方块向下移动 $1$ 格。 此时检查井中是否有方块，如果井中没有方块，游戏结束，玩家胜利，否则玩家开始放置下一个骨牌。 保证开始时最底下一行没有被方块填满。请判断玩家能否胜利，如果可能，则输出一种方案。

输入共 $N + 1$ 行。 第一行含有两个整数 $N,K$。 在接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）有一个整数 $A_i$。

如果玩家无法胜利，请输出一行一个 $-1$。 否则请输出 $X+1$ 行，其中 $X$ 表示消去所有棋子所需要的步数： 第一行包含一个整数 $X$。接下来第 $i$ 行（$1 \le i \le X$）表示你的方案。 - 如果第 $i$ 个下落的骨牌纵向放置，输出两个整数，第一个整数为 $1$，第二个整数 $x$ 表示玩家放置零件的位置（如题目描述中所述）。 - 如果第 $i$ 个下落的骨牌横向放置，输出两个整数，第一个整数为 $2$，第二个整数 $x$ 表示玩家放置零件的位置（如题目描述中所述）。

### 样例 1 解释  ### 数据规模与约定 **本题采用捆绑测试**。 对于所有数据，$2\le N\le 50$，$1\le K\le N$，$0\le A_i \le 50$。 - Subtask 1（15 points）：$K=2$ 且 $N$ 为奇数。 - Subtask 2（15 points）：$K=2$ 且 $N$ 为偶数。 - Subtask 3（15 points）：$K$ 能够整除 $N$。 - Subtask 4（55 points）：没有额外限制。