Problem D
Secret Sequence

There is a secret sequence of zeros and ones of length $n$, and you want to know the number of ones in the sequence. You are allowed to ask queries by giving four integers $0 \leq a \leq b \leq c \leq d \leq n$. The answer to the query will be $-1$ if the sum of the numbers at positions $a, a+1, ..., b-1$ is larger than the sum of the numbers at positions $c, c+1, ..., d-1$, and $1$ if the sum is smaller. If the sums are equal, the answer will be $0$.

The indices of the sequence start at $0$ and end at $n-1$. Note that the intervals you’re querying can be empty, if $a = b$ or $c = d$ respectively. The sum of the numbers in an empty interval is $0$.

Figure out the total number of ones in the sequence using at most $200$ queries.

Interactivity

This problem is interactive.

Your program should start by reading an integer $n$, the length of the sequence ($1 \le n \le 2 \cdot 10^5$).

Then for each query you make, you should print a single line containing a question mark (?) and four integers $0 \leq a \leq b \leq c \leq d \leq n$, separated by spaces. The grader will then read these numbers and in return print a line with either $-1$, $0$ or, $1$, which can be read by your program.

Your program should then repeat this until you want to guess how many ones there are, which you do by printing a line containing an exclamation mark (!) followed by a single integer number $x$, separated by a space. After you print this line, your program should terminate. If the number $x$ is correct, i.e. if it equals the number of ones in the sequence, you pass the test case.

You must make sure to flush standard output before reading the grader’s response, or else your program will get judged as Time Limit Exceeded. This works as follows in various languages:

• Java: System.out.println() flushes automatically.

• Python: print() flushes automatically.

• C++: cout << endl; flushes, in addition to writing a newline. If using printf, fflush(stdout).

The grader is not adaptive. That is, the numbers in the sequence are fixed for each test case and will not vary depending on your queries.

You can make at most $200$ ? queries.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Explanation of Sample 1

The secret sequence in this sample is $01101$, so $n = 5$, which is what the judge writes on the first line. The program then asks which number is greater: the first (at position $0$) or the last (at position $4$). The judge answers that the last number is greater, so we then know it has to be a one while the first number is a zero. After this, the program asks which is greater: the sum of the numbers at position $1$ and $2$ or the number at position $4$. The judge answers that the sum of the two numbers at position $1$ and $2$ is greater, and since we already know that there is a one at position $4$, this means both the numbers at position $1$ and $2$ are ones. Finally, the program asks which is greater: the number at position $0$ or the number at position $3$. The judge answers that they are the same, and so since the number at position $0$ is zero, which we know from the first query, this is also the case for the number at position $3$.

Hence there are $3$ ones in total, so the program answers this.

5

? 0 1 4 5

1

? 1 3 4 5

-1

? 0 1 3 4

0

! 3

2

? 0 1 1 2

0

? 0 1 1 1

-1

! 2