407385: GYM102780 I Andrew and Python

I. Andrew and Pythontime limit per test5.0 smemory limit per test256 MBinputstandard inputoutputstandard output

This is an interactive problem.

The first thing that a programming olympiad teacher should do is treat "the recruit" for a serious, but absolutely curable disease — pythonism.

Marat V. is a 'specialist' in the sphere of treatment of this disease, but, unfortunately, there is no so called "permanganate acid" to "treat" it. Then the teachers had no choice but to hide Andrew's knowledge of the ill-fated programming language in a very reliable place: the stash in the floor of the Room $$$113$$$.

The parquet in Room $$$113$$$ is a square with side $$$n - 1$$$ on the coordinate plane and contains $$$n^2$$$ points with natural coordinates. "The stash" is a point on the plane of the inner side of the square or on the side of the square. Andrew studies programming for the first year, so he does not know where it is. The only thing Andrew can do is ask stupid questions to his neighbor Zuckerman. There are three types of questions that he asks:

1) Andrew may ask about a specific point whether it is a stash;

2) Andrew may ask his neighbor about the segment given by the coordinates of its ends. However, the ends do not coincide — does the hidden point lie on this segment;

3) Andrew may ask his mate about the triangle formed by the coordinates of its vertices. The triangle is nondegenerate — does the hidden point lie inside or on the border of this triangle.

In any query, the coordinates of the points must be natural numbers.

Zuckerman, can answer the question either "Yes", or "No".

Andrew does not want his teachers to know that he is looking for his knowledge of the Python language, so he must ask no more than $$$60$$$ questions so that no one suspects anything.

Help Andrew guess the hidden point in the floor for no more than $$$60$$$ questions.

Interaction

First, your program receives one integer $$$n$$$ — the number of points on the side of the square where you want to search for a point ($$$1 \le n \le 10^8$$$).

After that, your program can make requests:

• In order to ask whether the point with the natural coordinates $$$(x, y)$$$ is the desired one (query type 1), you need to output it to the output stream in a separate line "? 1 $$$x$$$ $$$y$$$" .
• In order to ask whether the desired point lies on the segment with the ends at the natural points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ (query type 2), you need to output "? 2 $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$" into the output stream in a separate line.
• In order to ask whether the desired point lies inside the triangle with vertices at the natural points $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$(x_3, y_3)$$$ (request type 3), you need to output "? 3 $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$x_3$$$ $$$y_3$$$" into the output stream in a separate line.

In response to the request, the string "Yes" will be written in the input stream if the answer is positive, or "No", otherwise.

In any query, the coordinates of the points must be natural numbers and must not exceed $$$10^9$$$.

If your program makes more than $$$60$$$ requests or makes an incorrect request (for example, requests a degenerate triangle), it will receive any verdict other than "Accepted" .

Having determined at what point in the plane there is a stash with the knowledge of the Python language, your program should output "! $$$x$$$ $$$y$$$", where $$$(x, y)$$$ are the coordinates of the desired point.

It is guaranteed that the hidden point has natural coordinates, it is also the fixed kind of point and will not change during the testing of your program.

ExampleInput

3
No 
No 
No 
No 
Yes 
Yes

Output

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

Note

Output a line feed character after every action of your program. After printing each query you need to use special function to flush the output stream, because it is possible that some part of your output is left in the buffer. For example, you can use "fflush(stdout)" in C++, "System.out.flush()" in Java, "flush(output)" in Pascal and "stdout.flush()" in Python.

EXPLANATION TO THE EXAMPLE

In the test, a point with coordinates $$$(2, 2)$$$ (F in the figure) is given on a square with side 3. For convenience, the figure is presented.

The first query is whether the point belongs to the segment $$$(1, 1)$$$ $$$(3, 2)$$$ (AD in the figure). The answer is no.

The second query is whether the point belongs to the segment $$$(3, 1)$$$ $$$(2, 3)$$$ (CH in the figure). The answer is no.

The third query is whether the point belongs to the segment $$$(3, 3)$$$ $$$(1, 2)$$$ (IE in the figure). The answer is no.

The fourth query is whether the point belongs to the segment $$$(1, 3)$$$ $$$(2, 1)$$$ (GB in the picture). The answer is no.

The fifth query is whether the point belongs to the triangle $$$(1, 1)$$$ $$$(2, 3)$$$ $$$(3, 1)$$$ (AHC in the figure). The answer is yes.

The sixth query is whether point $$$(2, 2)$$$ is the required one. The answer is yes.

The displayed answer is ! 2 2.