Square or rectangle
Eolymp offers you to play an interesting interactive game "Square or Rectangle" with the testing system.
Eolymp has a square board of size cells. The lines of the board are numbered by integers from to from top to bottom, and the columns are numbered by integers from to from left to right. Accordingly, the cell that is located in the upper left corner of the board has coordinates ; the cell that is located in the lower right corner has coordinates ; and the cell that is located at the intersection of the -th row and -th column has coordinates .
Eolymp paints a rectangular area of the board, the upper left corner of which has coordinates , and the lower right — . Eolymp keeps these coordinates secret. But it is known that the area of the painted area is at least 4% of the area of the entire board.
You can ask Eolymp about any cell (whether it belongs to the painted area) and get an honest answer from the testing system. You need to find out if the painted area is a square.
Interaction
To find out if a cell belongs to the painted area, you need to ask Eolymp about it. To do this, you need to output the character "?", and two integers and — the coordinates of the point you want to ask about. After this, you need to output the character new line and perform the operation flush
. After this, you need to read a line. Eolymp will output either «inside
» if the cell is painted, or «outside
» otherwise.
fflush(stdout)
orcout.flush()
in C++;System.out.flush()
in Java;flush(output)
in Pascal;stdout.flush()
in Python;for all other languages you need to look at the documentation yourself.
You can ask no more than questions.
When you know the answer, you need to output the character "!", a space, and one of the two variants: either «square
» (if the figure painted by Eolimp is a square), or «rectangle
» (if the figure is a rectangle).
If you do not follow the format of interaction, you can receive any verdict: Wrong Answer
, Runtime Error
, Time Limit Exceeded
, etc.
Examples
inside inside outside inside outside outside inside outside outside
? 50 50 ? 75 75 ? 10 10 ? 20 20 ? 19 20 ? 20 19 ? 80 80 ? 81 80 ? 80 81 ! square
Note
In the example, Eolymp painted an area whose upper left corner is (20, 20), and the lower right corner is (80, 80).
The condition provides an example of how to interact with Eolymp. Your queries to Eolymp may be different.
Scoring
Your program will play this game with Eolymp many times. Let be the maximum number of questions you asked in all the games. Then you will receive such amount of points:
If you asked more than questions in any game, gave a wrong answer, or did not follow the format of interaction, you will receive points.
If , you will receive points.
If , you will receive points.
If , you will receive points.
If , you will receive points.
If , you will receive points.