You will be playing an interactive game in this problem.
The game is played on a square grid. Each cell of the grid is numbered with a pair , where and are the row and column number .
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 to cell .
Initially, you don't have any information about the grid. You have to find the location of the ship by performing the following operations:
? r c
In response, you will read a single character
S means the cell 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.
! r1 c1 r2 c2
Here, and are the cells that contain the two endpoints of the ship. You can print them in any order.
In the beginning, you will read an integer , 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):
In each subtask, You will get a "Wrong Answer" verdict if you use more queries than mentioned.
There are two types of output (details are already mentioned above):
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.
Login to submit