Bandit's Coins

"Parchet la minat!" — The Bandit

After an exhausting day of grueling work, Gaudeamus the miner finally leaves the Bandit's mine. For his hard labor, the Bandit pays him with exactly $N$ identical-looking coins. However, the miner is no stranger to the Bandit's tricks. From his past experiences, he knows for a fact that exactly one coin in his wage is a fake!

The counterfeit coin is either strictly lighter or strictly heavier (in which case it is strictly lighter than $2$ normal coins) than all the other genuine coins (which all share the exact same weight). Disposing of a classic balance scale, the miner wants to find the exact position of the fake coin.

Task

Help the miner locate the counterfeit coin using the minimum number of weighings!

Interaction protocol

This is an interactive problem. You can ask queries to the interactor through stdout and it will answer them through stdin.

First, your program must read a single integer $N$, representing the total number of coins. The coins are indexed from $1$ to $N$.

To weigh sets of coins, you must print a query on a single line in the following format:
? l1 r1 l2 r2

This operation places the continuous interval of coins $[l_1, r_1]$ on the left pan of the scale, and the continuous interval of coins $[l_2, r_2]$ on the right pan.

Then, after each query you make, you must read a single integer from the standard input, representing the scale's result:

• 0 — The scale is perfectly balanced (both sets have the same weight);
• 1 — The left pan is heavier than the right pan;
• 2 — The right pan is heavier than the left pan.

Once you have deduced the exact position $P$ of the fake coin, you must print the final answer in the following format:
! P

After printing the final answer, your program must terminate immediately.

Do not forget to flush the standard output after printing each query and the final answer. Otherwise, your program might receive a Time Limit Exceeded verdict. You can use:

• fflush(stdout) or cout.flush() or cout << endl in C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python.

Constraints and clarifications

• $3 \leq N \leq 10^9$
• For a query to be valid, the indices must respect the constraints $1 \leq l_1 \leq r_1 \leq N$ and $1 \leq l_2 \leq r_2 \leq N$. The two intervals placed on the scale must be completely disjoint ($r_1 < l_2$ or $r_2 < l_1$).
• Your program can use a maximum of 20 queries of type ?. Printing the final answer (!) does not count towards this limit.
• The interactor is adaptive. This means that the position of the fake coin may change depending on your queries but will not contradict previous queries.

Example

stdin

5
0
1

stdout

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

Explanation

The miner receives $5$ coins (secretly, the interactor has set coin $3$ to be heavier).

1. Your program starts by comparing coin $1$ (left) with coin $2$ (right).
2. The interactor answers 0. This means coins $1$ and $2$ have the same weight (both are genuine).
3. Your program reads 0. It then compares coin $3$ (left) with coin $1$ (genuine coin).
4. The interactor answers 1. Since coin $1$ is genuine, coin $3$ is the fake one.
5. The program reads 1. It correctly deduces position $3$, prints ! 3, and terminates.