题目背景

Looking at problems "K-Shaped Figures", "H-Shaped Figures" and "Eight-Shaped Figures" from the past three years, you might wonder what kind of geometry problem would be this year. To surprise you, this year the jury decides to change not the shape of the figure, but the "shape" itself. Today you need to find "Eight-$\textbf{connected}$ Figures" in real time.

题目描述

$\textit{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 $\textbf{randomly}$ colored either black or white with $50\%$ probability for each color, independently of other cells.

Two cells are considered $\textit{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 $\textit{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 $\textbf{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$).

Interaction Protocol

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:

• $\tt{?}$ $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: $\texttt{B}$ if the cell $(x, y)$ is black, or $\texttt{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:

• $\tt{!}$ $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 ($\texttt{B}$ for black and $\texttt{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 $\textbf{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.

2 5

W

W

B

B

B

W

B

B

B


B

W

W

B

B

W

W

W

B

? 1 1

? 1 2

? 1 3

? 2 1

? 2 2

? 2 3

? 3 1

? 3 2

? 3 3

! B 2 2 1 3 3 3 2 1 3 2
? 1 1

? 1 2

? 1 3

? 2 1

? 2 2

? 2 3

? 3 1

? 3 2

? 3 3

! W 1 2 3 2 1 3 2 3 3 1

提示

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.