P15054 [UOI 2023 II Stage] 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 $100 \times 100$ cells. The lines of the board are numbered by integers from $1$ to $100$ from top to bottom, and the columns are numbered by integers from $1$ to $100$ from left to right. Accordingly, the cell that is located in the upper left corner of the board has coordinates $(1,\,1)$; the cell that is located in the lower right corner has coordinates $(100,\,100)$; and the cell that is located at the intersection of the $i$-th row and $j$-th column has coordinates $(i,\,j)$. Eolymp paints a rectangular area of the board, the upper left corner of which has coordinates $(x_1,\,y_1)$, and the lower right --- $(x_2,\,y_2)$. 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. :::align{center}  ::: ### 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 $x$ and $y$ $(1 \le x \le 100, \; 1 \le y \le 100)$ --- the coordinates of the point you want to ask about. After this, you need to output the character new line and perform the operation $\tt{flush}$. After this, you need to read a line. Eolymp will output either $\tt{inside}$ if the cell is painted, or $\tt{outside}$ otherwise. - $\tt{fflush(stdout)}$ or $\tt{cout.flush()}$ in C++; - $\tt{System.out.flush()}$ in Java; - $\tt{flush(output)}$ in Pascal; - $\tt{stdout.flush()}$ in Python; - for all other languages you need to look at the documentation yourself. You can ask no more than $10\,000$ questions. When you know the answer, you need to output the character "!", a space, and one of the two variants: either $\tt{square}$ (if the figure painted by Eolimp is a square), or $\tt{rectangle}$ (if the figure is a rectangle). If you do not follow the format of interaction, you can receive any verdict: $\tt{Wrong\ Answer}$, $\tt{Runtime\ Error}$, $\tt{Time\ Limit\ Exceeded}$, etc.

N/A

N/A

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. Your program will play this game with Eolymp many times. Let $q$ 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 $10\,000$ questions in any game, gave a wrong answer, or did not follow the format of interaction, you will receive $0$ points. - If $1\,000 < q \leq 10\,000$, you will receive $5$ points. - If $100 < q \leq 1\,000$, you will receive $19$ points. - If $50 < q \leq 100$, you will receive $20 + \lfloor\frac{(100 - q) \cdot 30}{50}\rfloor$ points. - If $33 < q \leq 50$, you will receive $50 + \lfloor\frac{(50 - q) \cdot 50}{17}\rfloor$ points. - If $q \leq 33$, you will receive $100$ points.