Assiut Chess

**本题是一道交互题。** **本题需要你编写一个国际象棋中单后杀王的程序，和交互库对弈。** 本题的规则和一般国际象棋中的规则有所不同，请认真阅读。 国际象棋棋盘是 $8\times 8$ 的正方形网格。本题中，所有行从上到下分别编为 $1\sim 8$ 行，所有列从左到右分别编为 $1\sim 8$ 列；记同时处在第 $r$ 行、第 $c$ 列的格子为格子 $(r,c)$。 在游戏的开始，你需要确定并告知交互库皇后的初始坐标。接着，交互库会秘密地把国王放至棋盘上任何一个格子。然后，游戏开始，双方轮流走棋，由交互库先行。 皇后的 **行走范围** 为所有和皇后同行、同列或者同在一条 $45^\circ$ 斜线上的格子。也就是说，设皇后当前在格子 $(r,c)$，则皇后下一步能走到格子 $(x,y)$，当且仅当 $(r,c)\neq (x,y)$，且 $r=x$ 或 $c=y$ 或 $|r-x|=|c-y|$。注意：在一步棋中，不允许将皇后停在原地不动。 国王的 **行走范围** 为其紧邻的 $8$ 个格子。也就是说，也就是说，设国王当前在格子 $(r,c)$，则国王下一步能走到格子 $(x,y)$，当且仅当 $(r,c)\neq (x,y)$，且 $\max \{|r-x|,|c-y|\}=1$。**国王不能停在原地不动，不能走入皇后所在的格子，也不能走入皇后的行走范围中。** 如果国王无法移动，那么游戏结束，你获得胜利。特别地，如果游戏开始时国王和皇后处于同一位置，那么你直接获胜。 游戏开始后，你和交互库将通过输入输出交流各自走棋的位置（具体格式见下文）。你需要在 $130$ 步内获得胜利，如果你在行走 $130$ 步后国王仍有合法移动，那么视作你失败。你需要写一个程序，在规定的步数内获得胜利。 ### 交互细节 本题一个测试点含多组测试数据。你需要首先从标准输入中读入一个正整数 $t(1\leq t\leq 60)$，表示测试数据组数。你们接下来将进行 $t$ 次游戏。 每次游戏开始时，你需要先输出两个正整数 $x\ y$，表示你选择的皇后坐标。接着交互库会选择国王的坐标（但不会告诉你）。接着从交互库开始，双方轮流行动。 当交互库行动时，你需要读入一个字符串 $S$。$S$ 的取值可能有如下几种： - `Done`：表示交互库无法找到合适的着法，你获胜。如果是最后一组数据则请退出程序；否则请准备下一组数据。 - `Right`，`Left`，`Up`，`Down`，`Down-Right`，`Down-Left`，`Up-Right`，`Up-Left`：分别表示国王向右、左、上、下、右下、左下、右上、左上走了一步。 当你行动时，你需要输出两个整数 $x\ y$ 表示你移动到的坐标。你需要保证坐标合法。

This is an interactive problem. ICPC Assiut Community decided to hold a unique chess contest, and you were chosen to control a queen and hunt down the hidden king, while a member of ICPC Assiut Community controls this king. You compete on an $ 8\times8 $ chessboard, the rows are numerated from top to bottom, and the columns are numerated left to right, and the cell in row $ x $ and column $ y $ is denoted as $ (x, y) $ . In one turn you can move the queen to any of the squares on the same horizontal line, vertical line, or any of the diagonals. For example, if the queen was on square ( $ 4 $ , $ 5 $ ), you can move to ( $ q_1 $ , $ 5 $ ), ( $ 4 $ , $ q_1 $ ), ( $ q_1 $ , $ 9-q_1 $ ), or ( $ q_2 $ , $ q_2+1 $ ) where ( $ 1 \le q_1 \le 8 $ , $ q_1 \ne 4 $ , $ 1 \le q_2 \le 7 $ , $ q_2 \ne 4 $ ). Note that the queen cannot stay on its current cell. In one turn, the king can move "Right", "Left", "Up", "Down", "Down-Right", "Down-Left", "Up-Left", or "Up-Right" such that he doesn't get out of the board. The king cannot move into a cell that is on the same row, column or diagonal with the queen (including the position of the queen itself). For example, if the king was on square ( $ 4 $ , $ 5 $ ), he can move to ( $ 4+k_1 $ , $ 5+k_2 $ ) where ( $ -1 \le k_1,k_2 \le 1 $ , $ (k_1, k_2) \ne (0, 0) $ ). At the start of the game, you should place the queen at any location on the board, and this is done once per game. After that the king is secretly placed at any cell different from the queen's location. You do not know the position of the king. Then, the king and the queen take turns with the king moving first. The king moves to one of the possible directions ("Right", "Down", "Up-Left", etc.), and you are only given the direction it moves to. After that, you should move your queen by declaring the square to which your queen will move. The game follows like this until you win the game or run out of moves. You win if the king has no valid moves. You lose if after $ 130 $ moves of the queen the king still has valid moves.

The first line contains a single integer $ t $ ( $ 1 \le t \le 60 $ ) — the number of test cases.

In each test case, you should print the queen's starting cell immediately. If you placed the queen at the king's cell, you will win immediately. After that, you may make at most $ 130 $ moves. Each move is made in the format $ x $ $ y $ , where $ x $ and $ y $ are two integers ( $ 1 \leq x,y \leq 8 $ ) that denote the new row and column of the queen respectively. Your move should be a valid queen move. After the initial queen placement and after each move you will receive a string $ s $ that represents the direction of the king's move. It will be one of the following: "Right", "Left", "Up", "Down", "Down-Right", "Down-Left", "Up-Left", "Up-Right", or "Done" if you win the game. You should consider "Done" as the end of each test case. After printing a query 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. If at any point you make an invalid query or try to make more than $ 130 $ queries for each test case, the game will terminate immediately and you will receive a Wrong Answer verdict.

1
Left
Right
Done

7 5
7 6
7 7

In the example, the hidden king was at $ (8, 8) $ at the start. The game follows like this: