Dasha and Chess

题意翻译

### 题目大意 交互题 $999 \times 999$的棋盘上，有一个白王和$666$个黑车，每次白王可以往$8$个方向走一格，黑车可以随便移动到某个没有棋子的位置，当黑车移动后白王和某个黑车在同一行/列时白王赢，求白王在$2000$步之内的必胜策略 ### 输入格式 先开始共$667$行 第一行两个整数$x,y$，表示白王初始位置 第$2$到$667$行，每行两个整数$x_i,y_i$，表示黑车初始位置 然后根据你的输出，每次读入$3$个整数$k,x,y$，表示编号为$k$的黑车移动到$(x,y)$ 如果$k=-1$，说明你找到了必胜策略；如果$k=0$，说明白王飞出了棋盘 这两种情况你都应该结束程序qaq 因为输入这么多行所以你甚至不能测样例 ### 输出格式 每一步，你需要输出两个整数$X,Y$，表示白王移动到了位置$(X,Y)$，值得注意的是，黑车的移动会根据白王的移动来制定最优策略（应该是最优的……吧？）

题目描述

This is an interactive task. Dasha and NN like playing chess. While playing a match they decided that normal chess isn't interesting enough for them, so they invented a game described below. There are $ 666 $ black rooks and $ 1 $ white king on the chess board of size $ 999 \times 999 $ . The white king wins if he gets checked by rook, or, in other words, if he moves onto the square which shares either a row or column with a black rook. The sides take turns, starting with white. NN plays as a white king and on each of his turns he moves a king to one of the squares that are adjacent to his current position either by side or diagonally, or, formally, if the king was on the square $ (x, y) $ , it can move to the square $ (nx, ny) $ if and only $ \max (|nx - x|, |ny - y|) = 1 $ , $ 1 \leq nx, ny \leq 999 $ . NN is also forbidden from moving onto the squares occupied with black rooks, however, he can move onto the same row or column as a black rook. Dasha, however, neglects playing by the chess rules, and instead of moving rooks normally she moves one of her rooks on any space devoid of other chess pieces. It is also possible that the rook would move onto the same square it was before and the position wouldn't change. However, she can't move the rook on the same row or column with the king. Each player makes $ 2000 $ turns, if the white king wasn't checked by a black rook during those turns, black wins. NN doesn't like losing, but thinks the task is too difficult for him, so he asks you to write a program that will always win playing for the white king. Note that Dasha can see your king and play depending on its position.

输入输出格式

输入格式

In the beginning your program will receive $ 667 $ lines from input. Each line contains two integers $ x $ and $ y $ ( $ 1 \leq x, y \leq 999 $ ) — the piece's coordinates. The first line contains the coordinates of the king and the next $ 666 $ contain the coordinates of the rooks. The first coordinate denotes the number of the row where the piece is located, the second denotes the column. It is guaranteed that initially the king isn't in check and that all pieces occupy different squares.

输出格式

After getting king checked, you program should terminate immediately without printing anything extra. Interaction To make a move with the king, output two integers $ x $ and $ y $ ( $ 1 \leq x, y \leq 999 $ ) — the square to which the king would be moved. The king cannot move onto the square already occupied by a rook. It is guaranteed that the king would always have a valid move. After each of your turns read the rook's turn in the following format: a single line containing three integers $ k $ , $ x $ and $ y $ ( $ 1 \leq k \leq 666 $ , $ 1 \leq x_i, y_i \leq 999 $ ) — the number of the rook that would move and the square it would move to. It is guaranteed that the rook wouldn't move to a square already occupied by another chess piece, but it can move onto the square where it was before the turn so that its position wouldn't change. It is guaranteed that the move does not put your king into a check. If your king got in check, all three integers would be equal to $ -1 $ and in that case your program should terminate immediately. After printing your turn 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. Answer "0 0 0" instead of a correct answer means that you made an invalid query. Exit immediately after receiving "0 0 0" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream. Hacks are not allowed for this problem.

输入输出样例

输入样例 #1

999 999
1 1
1 2
2 1
2 2
1 3
2 3
<...>
26 13
26 14
26 15
26 16

1 700 800

2 1 2

<...>

-1 -1 -1

输出样例 #1

999 998

999 997

<...>

999 26

说明

The example is trimmed. The full initial positions of the rooks in the first test are available at <https://pastebin.com/qQCTXgKP>. It is not guaranteed that they will behave as in the example.