Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Find the Ship

By shahed95 · Limits 5s, 512 MB · Interactive

You will be playing an interactive game in this problem.

The game is played on a 7×77\times 7 square grid. Each cell of the grid is numbered with a pair (ri,ci)(r_i,c_i), where rir_i and cic_i are the row and column number (1ri,ci7)(1\leq r_i, c_i \leq 7).

The grid is covered with water and there is a ship inside it. The ship covers exactly 4 consecutive cells of the grid (either vertically or horizontally).
Check the picture below to get a clear idea:


In this figure, the ship is located on cell (6,4)(6,4) to cell (6,7)(6,7).

Initially, you don't have any information about the grid. You have to find the location of the ship by performing the following operations:

  • You can ask whether a cell (r,c)(r, c) contains some part of the ship. To do it, print a line in the following format:
? r c

In response, you will read a single character S or W, where S means the cell (r,c)(r, c) contains some part of the ship and W means it contains water.
There will be a limitation on the number of queries you can perform, see the subtasks portion for more details.

  • You have to end the interaction by printing the ship location. To do it, print a line in the following format:
! r1 c1 r2 c2

Here, (r1,c1)(r1, c1) and (r2,c2)(r2, c2) are the cells that contain the two endpoints of the ship. You can print them in any order.

Input

In the beginning, you will read an integer T(1T10000)T (1\leq T\leq 10000), the number of test cases. Interaction for the first test case will start right after that.

You will read one of the following as a response of query operation (details are already mentioned above):

  • S
  • W

Subtasks

  • Subtask 1 (35 points): Perform no more than 13 queries for each case.
  • Subtask 2 (65 points): Perform no more than 12 queries for each case.

In each subtask, You will get a "Wrong Answer" verdict if you use more queries than mentioned.

Output

There are two types of output (details are already mentioned above):

  1. ? r c
  2. ! r1 c1 r2 c2

After printing the ship location, interaction for the next test case will start (if there is any).

Here is what a possible interaction would look like:

> 2
< ? 1 1
> S
< ? 1 2
> S
< ! 1 1 1 4
< ? 1 1
> W
< ? 1 2
> S
< ? 1 3
> W
< ! 1 2 4 2

>indicates what your program reads and < indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.

Discussion

Statistics


43% Solution Ratio

lelbabaEarliest, 1M ago

lelbabaFastest, 0.2s

shahed95Lightest, 164 kB

shahed95Shortest, 1698B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.