A10474 | Searching Rectangles

The first line of the input contains an integer $n$ ( $2<=n<=2^{16}$ ) — size of the field.

For each query an integer between $0$ and $2$ is returned — the number of initial rectangles that lie fully inside the query rectangle.

To make a query you have to print "? $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ " (without quotes) ( $1<=x_{1}<=x_{2}<=n$ , $1<=y_{1}<=y_{2}<=n$ ), where $(x_{1},y_{1})$ stands for the position of the bottom left cell of the query and $(x_{2},y_{2})$ stands for the up right cell of the query. You are allowed to ask no more than $200$ queries. After each query you should perform "flush" operation and read the answer.

In case you suppose you've already determined the location of two rectangles (or run out of queries) you should print "! $x_{11}$ $y_{11}$ $x_{12}$ $y_{12}$ $x_{21}$ $y_{21}$ $x_{22}$ $y_{22}$ " (without quotes), where first four integers describe the bottom left and up right cells of the first rectangle, and following four describe the corresponding cells of the second rectangle. You can print the rectangles in an arbitrary order. After you have printed the answer, print the end of the line and perform "flush". Your program should terminate immediately after it print the answer.

Interaction

To flush you can use (just after printing an integer and end-of-line):

- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
- See the documentation for other languages.

You will get the Wrong Answer verdict if you ask more than $200$ queries, or if you print an incorrect coordinates.

You will get the Idleness Limit Exceeded verdict if you don't print anything (but you should) or if you forget about flushing the output (more info below).

Hacking.

The first line should contain an integer $n$ ( $2<=n<=2^{16}$ ).

The second line should contain four integers $x_{1}$ , $y_{1}$ , $x_{2}$ , $y_{2}$ ( $1<=x_{1}<=x_{2}<=n$ , $1<=y_{1}<=y_{2}<=n$ ) — the description of the first rectangle.

The third line contains the description of the second rectangle in the similar way.

无