CF1503B.3-Coloring

This is an interactive problem.

Alice and Bob are playing a game. There is $n\times n$ grid, initially empty. We refer to the cell in row $i$ and column $j$ by $(i, j)$ for $1\le i, j\le n$. There is an infinite supply of tokens that come in $3$ colors labelled $1$, $2$, and $3$.

The game proceeds with turns as follows. Each turn begins with Alice naming one of the three colors, let's call it $a$. Then, Bob chooses a color $b\ne a$, chooses an empty cell, and places a token of color $b$ on that cell.

We say that there is a conflict if there exist two adjacent cells containing tokens of the same color. Two cells are considered adjacent if they share a common edge.

If at any moment there is a conflict, Alice wins. Otherwise, if $n^2$ turns are completed (so that the grid becomes full) without any conflicts, Bob wins.

We have a proof that Bob has a winning strategy. Play the game as Bob and win.

The interactor is adaptive. That is, Alice's color choices can depend on Bob's previous moves.

Interaction

The interaction begins by reading a single integer $n$ ($2\le n\le 100$) — the size of the grid.

The turns of the game follow. You should begin each turn by reading an integer $a$ ($1\le a\le 3$) — Alice's chosen color.

Then you must print three integers $b,i,j$ ($1\le b\le 3,b\ne a, 1\le i,j\le n$) — denoting that Bob puts a token of color $b$ in the cell $(i, j)$. The cell $(i, j)$ must not contain a token from a previous turn. If your move is invalid or loses the game, the interaction is terminated and you will receive a Wrong Answer verdict.

After $n^2$ turns have been completed, make sure to exit immediately to avoid getting unexpected verdicts.

After printing something do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hack Format

To hack, use the following format.

The first line contains a single integer $n$ ($2\le n\le 100$).

The second line contains $n^2$ integers $a_1,\ldots,a_{n^2}$ ($1\le a_i\le 3$), where $a_i$ denotes Alice's color on the $i$-th turn.

The interactor might deviate from the list of colors in your hack, but only if it forces Bob to lose.

这是一个交互式问题。

爱丽丝（Alice）和鲍勃（Bob）正在玩一个游戏。有一个 $n\times n$ 的网格，初始时为空。我们将第 $i$ 行、第 $j$ 列的格子记为 $(i, j)$，其中 $1\le i, j\le n$。有无限供应的标记物（token），共 $3$ 种颜色，分别标号为 $1$、$2$ 和 $3$。

游戏按回合进行，规则如下：每回合开始时，爱丽丝指定三种颜色之一，记作 $a$；随后鲍勃选择一个与 $a$ 不同的颜色 $b$（即 $b \ne a$），再选择一个空格子，并在该格子上放置一个颜色为 $b$ 的标记物。

若存在两个相邻格子，其上的标记物颜色相同，则称出现冲突。两个格子相邻当且仅当它们共享一条公共边。

若在任意时刻发生冲突，则爱丽丝获胜；否则，若经过 $n^2$ 回合后网格被填满且始终无冲突，则鲍勃获胜。

我们已证明：鲍勃存在必胜策略。请以鲍勃的身份参与游戏并获胜。

交互器是自适应的，即爱丽丝每轮选择的颜色可依赖于鲍勃此前的所有操作。

交互流程

交互开始时，先读入一个整数 $n$（$2\le n\le 100$）——表示网格大小。

随后进入游戏回合。每回合开始时，你需要先读入一个整数 $a$（$1\le a\le 3$）——即爱丽丝本轮选定的颜色。

接着，你必须输出三个整数 $b,i,j$（$1\le b\le 3$，$b\ne a$，$1\le i,j\le n$），表示鲍勃将一个颜色为 $b$ 的标记物放入格子 $(i, j)$。格子 $(i, j)$ 必须在此前未被占用。若你的操作非法（如 $b = a$、$(i,j)$ 已被占用、越界等）或导致失败（如引发冲突），交互将立即终止，你将收到“Wrong Answer”判据。

当完成全部 $n^2$ 回合后，请立即退出程序，以免获得非预期的判据。

每次输出后，务必输出换行符并刷新输出缓冲区，否则将收到 “Idleness limit exceeded”。具体方法如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请查阅相应文档。

Hack 格式

用于 Hack 时，请采用如下格式：

第一行包含一个整数 $n$（$2\le n\le 100$）。

第二行包含 $n^2$ 个整数 $a_1,\ldots,a_{n^2}$（$1\le a_i\le 3$），其中 $a_i$ 表示爱丽丝在第 $i$ 回合所选的颜色。

交互器在 Hack 过程中可能不严格遵循你提供的颜色序列，但仅当该偏离会导致鲍勃失败时才会如此。

The final grid from the sample is pictured below. Bob wins because there are no two adjacent cells with tokens of the same color. $$\begin{matrix}2&3\\3&1\end{matrix}$$

The sample is only given to demonstrate the input and output format. It is not guaranteed to represent an optimal strategy for Bob or the real behavior of the interactor.

示例的最终网格如下图所示。鲍勃获胜，因为不存在两个相邻的格子中放置了相同颜色的棋子。

$$\begin{matrix}2&3\\3&1\end{matrix}$$

该示例仅用于说明输入与输出格式。不能保证其体现了鲍勃的最优策略，也不能保证其反映了交互器的真实行为。