19013번 - Binary String 다국어인터랙티브

This is an interactive problem.

The jury has a secret string which consists of exactly $1000$ binary digits. In each test for this problem, the string is fixed in advance and does not change. You have to find this string using queries.

In each query, you choose a segment $[a, b]$ ($1 \leq a \leq b \leq 1000$) to ask about. Then the jury flips a coin, and gives you one of the two values, each with probability of 50%:

1. The number of $1$s in the segment $[a, b]$; 
2. A value from $0$ to $b - a + 1$ which is not equal to the number of ones on this segment, chosen uniformly at random.

You are not allowed to use the same query twice. All random values used in this problem are uniform and independent.

The participant program must interact with the jury program by printing commands in one of the following formats: 

• "? $a$ $b$". A query for the segment $[a, b]$. To answer this query, the jury program will output a single integer which will, with probability 50%, be either the number of $1$s in the segment $[a, b]$ or a random value from $0$ to $b - a + 1$ not equal to it.
• "! $\mathit{ans}$". The answer to the problem, where $\mathit{ans}$ is a string of length $1000$ consisting of $0$s and $1$s. After this command, the participant program should terminate immediately.

Your solution can make at most 18,000 queries.

The example above is given only to demonstrate the format. In this example, the string has length $5$. In the real first test, as well as all other tests, the length of the string to guess is exactly $1000$.