题目描述

这是一道交互题。你的程序需要通过标准输入、标准输出与评测程序交互。

评测程序想和你的程序玩一个游戏。在一个 $n\times n$ 的棋盘上，有两枚棋子分别位于两个不同的格子中。你的程序需要确定这两枚棋子的初始位置。

为了确定位置，你可以尝试移动棋子。每次操作中，你选择其中一枚棋子，并要求它向左、向右、向上或向下移动一格。评测程序会告诉你这次移动是否成功：

• 如果目标格子存在且当前没有棋子，则移动成功，棋子移动到该格；
• 否则移动失败，棋子保持原位。

当你的程序认为已经确定了两枚棋子的初始位置时，可以输出答案。你需要在不超过 $6n$ 次移动操作内获胜。

棋盘坐标定义如下：所有格子的坐标为

$$(1,1),(1,2),\ldots,(1,n),(2,1),\ldots,(n,n).$$

方向字符含义如下：

• U：从 $(x,y)$ 移动到 $(x,y+1)$；
• D：从 $(x,y)$ 移动到 $(x,y-1)$；
• R：从 $(x,y)$ 移动到 $(x+1,y)$；
• L：从 $(x,y)$ 移动到 $(x-1,y)$。

交互协议

交互开始时，评测程序会向你的程序输出一个整数 $n$，表示棋盘大小。

$$2\le n\le 50.$$

随后你的程序可以反复输出以下两类命令之一。

1. 移动棋子

若要尝试移动一枚棋子，输出：

0 id c

其中：

• $id$ 为棋子编号，只能是 1 或 2；
• $c$ 为移动方向，只能是 U、D、L、R 之一。

每次移动命令之后，评测程序会返回一个整数：

• 1：移动成功；
• 0：移动失败。

一次移动命令计为一次操作。总移动次数不得超过 $6n$。

2. 回答初始位置

若你的程序已经确定答案，输出：

1 x1 y1 x2 y2

表示第一枚棋子的初始位置是 $(x_1,y_1)$，第二枚棋子的初始位置是 $(x_2,y_2)$。

需要满足：

$$1\le x_1,y_1,x_2,y_2\le n.$$

输出该命令后，程序应立即结束。

如果答案正确且移动次数不超过 $6n$，则通过该测试点；否则会得到错误结果。

样例

下面样例仅用于说明交互过程。样例中隐藏的初始位置为第一枚棋子在 $(1,1)$，第二枚棋子在 $(2,2)$。

评测程序输出 / 选手程序输入

2
0
1
0
1

选手程序输出 / 评测程序输入

0 1 L
0 1 U
0 1 L
0 2 D
1 1 1 2 2

样例解释

交互过程如下：

1. 评测程序先输出 2，表示棋盘大小为 $2\times 2$。
2. 选手输出 0 1 L，尝试将 1 号棋子向左移动，失败，评测程序返回 0。
3. 选手输出 0 1 U，尝试将 1 号棋子向上移动，成功，评测程序返回 1。
4. 选手输出 0 1 L，再次尝试将 1 号棋子向左移动，失败，评测程序返回 0。
5. 选手输出 0 2 D，尝试将 2 号棋子向下移动，成功，评测程序返回 1。
6. 选手输出 1 1 1 2 2，报告两枚棋子的初始位置。

重要提示

每次输出后都必须换行并刷新输出缓冲区。

在 C++ 中可以使用：

cout << ... << endl;

或者手动使用：

cout.flush();

常见错误原因包括：

• 没有在每次输出后刷新缓冲区，导致程序空闲超时；
• 输出格式错误；
• 移动次数超过 $6n$；
• 最终给出的初始坐标错误。