I. RMQ
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Busy Beaver has a secret array $$$a_1,a_2,\dots,a_N$$$ of distinct positive integers between $$$1$$$ and $$$10^9$$$. For $$$1 \le l \le r \le N$$$, Busy Beaver defines $$$f(l,r)$$$ to be equal to $$$\min(a_l,a_{l+1},\dots,a_r)$$$.

Busy Beaver allows you to ask some queries to uncover information about the array. In a query, you can specify $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le N$$$), and Busy Beaver will tell you the value of $$$f(l,r)$$$ for a cost of $$$\frac{1}{r-l+1}$$$. You must ensure that the total cost of all queries is at most $$$1$$$.

After making all your queries, you report to Busy Beaver a list of pairs $$$(l,r)$$$ for which you determined the value of $$$f(l,r)$$$. If any of your answers are wrong, Busy Beaver will be displeased and award you $$$0$$$ points. Otherwise, your score will depend on the fraction of the $$$\frac{N(N+1)}{2}$$$ pairs $$$(l,r)$$$ with $$$1 \le l \le r \le N$$$ where you determined a value for $$$f(l,r)$$$ (see the Scoring section for more details).

To reduce the size of the output, you report your knowledge using $$$k$$$ tuples of the form $$$(l_{min},l_{max},r_{min},r_{max},v)$$$, where $$$1 \le l_{min} \le l_{max} \le r_{min} \le r_{max} \le N$$$ and $$$1 \le v \le 10^9$$$. Each tuple declares that $$$f(l,r) = v$$$ for all $$$l_{min} \le l \le l_{max}$$$ and $$$r_{min} \le r \le r_{max}$$$. Any pairs $$$(l,r)$$$ that do not correspond to any tuple are treated as unspecified. It is allowed to have multiple tuples that describe the same pair $$$(l,r)$$$, but you will receive $$$0$$$ points if these tuples indicate inconsistent values.

Interaction

The first line of input contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$), the length of Busy Beaver's secret array.

You may repeatedly ask queries by outputting a line of the form "? l r", where $$$1 \le l \le r \le N$$$. Then, the judge will respond with a single integer, denoting the value of $$$f(l,r)$$$. If you exceed a total cost of $$$1$$$, the judge will instead respond with $$$-1$$$, and you should terminate your program immediately to receive a Wrong Answer verdict.

After you are finished with your queries, first output a line of the form "! k" ($$$0 \le k \le 2N$$$), representing that you will describe your knowledge of $$$f$$$ using $$$k$$$ tuples $$$(l_{min},l_{max},r_{min},r_{max},v)$$$.

Then, the next $$$k$$$ lines should each contain $$$5$$$ space-separated integers $$$l_{min}$$$, $$$l_{max}$$$, $$$r_{min}$$$, $$$r_{max}$$$, and $$$v$$$, specifying a tuple.

The interactor is not adaptive, meaning that Busy Beaver will not change the entries of his secret array $$$a$$$ in response to your queries.

Scoring

For all test cases used for scoring, $$$N = 10^5$$$.

If you exceed a cost of $$$1$$$ or any of the values you claim for $$$f(l,r)$$$ are incorrect, you will receive $$$0$$$ points and a Wrong Answer verdict.

Otherwise, let $$$x$$$ be the fraction of the $$$\frac{N(N+1)}{2}$$$ values of $$$f(l,r)$$$ that you specified a value for. Your score for the test case will be equal to $$$$$$ \left\lfloor \min\left(100,100 \cdot \frac{x}{0.8}\right) \right\rfloor. $$$$$$ In particular, if $$$x \ge 0.8$$$, then you will receive full points for the test case.

Your final score will be the minimum score over all test cases.

Example
Input
6

31

26

53
Output

? 1 3

? 1 6

? 5 6

! 4
1 1 3 3 31
1 4 4 6 26
2 3 5 5 26
5 5 6 6 53
Note

Note that the sample does not satisfy $$$N = 10^5$$$, so it will not be included in the actual test cases. It is provided only to illustrate the interaction format.

In the sample, Busy Beaver's secret array is $$$a = [31,41,59,26,53,58]$$$. You decide to make the following queries:

  • $$$l = 1$$$, $$$r = 3$$$: Busy Beaver calculates $$$f(1,3) = \min(31,41,59) = 31$$$ and tells you the value $$$31$$$.
  • $$$l = 1$$$, $$$r = 6$$$: Busy Beaver calculates $$$f(1,6) = \min(31,41,59,26,53,58) = 26$$$ and tells you the value $$$26$$$.
  • $$$l = 5$$$, $$$r = 6$$$: Busy Beaver calculates $$$f(5,6) = \min(53,58) = 53$$$ and tells you the value $$$53$$$.

Note that the total cost of all your queries is $$$\frac13+\frac16+\frac12 = 1$$$, which does not exceed $$$1$$$ as required.

From this information, you report to Busy Beaver the following values of $$$f(l,r)$$$ you have deduced:

  • $$$f(l,r) = 31$$$ for all $$$1 \le l \le 1$$$, $$$3 \le r \le 3$$$.
  • $$$f(l,r) = 26$$$ for all $$$1 \le l \le 4$$$, $$$4 \le r \le 6$$$.
  • $$$f(l,r) = 26$$$ for all $$$2 \le l \le 3$$$, $$$5 \le r \le 5$$$. This overlaps with the information in the previous line, but is a valid output.
  • $$$f(l,r) = 53$$$ for all $$$5 \le l \le 5$$$, $$$6 \le r \le 6$$$.
After removing overlaps, you reported $$$14$$$ of the values of $$$f(l,r)$$$ out of the $$$\frac{N(N+1)}{2} = 21$$$ distinct pairs $$$(l,r)$$$. Therefore, Busy Beaver will calculate $$$x = \frac{14}{21}$$$ and give you a score of $$$$$$ \left\lfloor 100 \cdot \frac{14/21}{0.8} \right\rfloor = \left\lfloor 83.\bar{3} \right\rfloor = 83 $$$$$$ for this interaction.