35022번 - Eight-Connected Figures 다국어인터랙티브

문제

This is an interactive problem.

An infinite square grid is hidden from you. Every cell is identified by a pair of integers $(x, y)$ and is randomly colored either black or white with 50ドル\%$ probability for each color, independently of other cells.

Two cells are considered adjacent if they share an edge or a corner. Thus, every cell $(x, y)$ has 8ドル$ adjacent cells: $(x-1, y-1),ドル $(x-1, y),ドル $(x-1, y+1),ドル $(x, y-1),ドル $(x, y+1),ドル $(x+1, y-1),ドル $(x+1, y),ドル and $(x+1, y+1)$.

A set of cells $S$ is called 8-connected if for any two cells in $S,ドル there exists a path between them using only cells from $S,ドル where consecutive cells in the path are adjacent.

In one query, you can learn the color of any cell on the grid. Your task is to find an 8-connected set of $n$ cells such that all cells in the set have the same color.

You need to solve $t$ test cases. In each test case, the grid is colored randomly and independently of the other test cases.

You are allowed to make at most 30ドル,000円$ queries in total over all test cases.

입력

The first line contains two integers $t$ and $n,ドル denoting the number of test cases and the required size of the 8-connected set (1ドル \le t \le 50$; 2ドル \le n \le 300$).

출력

제한

인터랙션 프로토콜

In each test case, you can make zero or more queries to learn the colors of grid cells.

To make a query, print a line:

• ? $x$ $y$

where $(x, y)$ are the coordinates of the requested cell ($-10^9 \le x, y \le 10^9$). After that, read a line containing one letter: 'B' if the cell $(x, y)$ is black, or 'W' if the cell $(x, y)$ is white.

Once you are ready to present an 8-connected set of $n$ cells of the same color, print a line:

• ! $c$ $x_1$ $y_1$ $x_2$ $y_2$ $\ldots$ $x_n$ $y_n$

where $c$ is a letter denoting the color of the cells in the set ('B' for black and 'W' for white), and $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ are the $n$ distinct cells in the set ($-10^9 \le x_i, y_i \le 10^9$). The interactor does not print anything in response to this line.

After printing the set, proceed to the next test case, or terminate the program if this was the last one.

You are allowed to make at most 30ドル,000円$ queries in total over all test cases (not including the lines that print the sets). If you exceed this limit, the interactor will print 0ドル$ instead of its usual response, and your program should terminate immediately to guarantee the "Wrong Answer" verdict.

The interactor is not adaptive: all random grids used in the tests have been pre-generated and remain the same across all submissions.

노트

In the example, the queries and the responses are separated by empty lines for clarity. In the actual interaction between your program and the interactor, there will be no empty lines.

Your solution will be evaluated on at most 60ドル$ test files.