Problem E
Skyline Reconstruction

From a ridge outside the city, you observe a straight line of $n=2025$ tall buildings at night. Some buildings have an enhanced security beacon on their roof. From this distance, you cannot identify individual beacons, but your device can report an illumination coefficient for any contiguous frame of buildings you choose.

Your task is to recover the full skyline — for every building, determine whether it has a beacon — using at most $\mathbf{405}$ queries.

Let $s_1, \dots , s_n \in \{ 0,1\} $ be the hidden skyline, where $s_i = 1$ if and only if building $i$ has a beacon. For a query frame $[l,r]$ with $1 \le l \le r \le n$, the device returns the integer

the total number of beaconed buildings counted across all contiguous subframes $[x,y] \subseteq [l,r]$. (Notation: $[x,y]$ is inclusive, and $\# \{ \cdot \} $ denotes set cardinality.)

Interaction

Your program communicates with the judge as follows:

• Query a frame $[l,r]$:

  ? l r
  

  The judge replies with a single integer $C(l,r)$.

• Output the recovered skyline (then terminate):

  ! s
  

  where s is a binary string of length $n$ (1 if the corresponding building has a beacon, 0 otherwise).

All indices are 1-based and inclusive.

Limits

• Your program will be run on exactly 100 test cases.

• Each test case consists of a uniformly random binary string of length $n=2025$. The interactor is not adaptive: the hidden string for each case is fixed before your program execution.

• You may perform at most $\mathbf{405}$ queries. Reporting the final answer does not count toward this query limit.

• Each query must satisfy $1 \le l \le r \le n$, and there should be no extraneous output. Remember to flush after every output.

• If the judge ever responds with -1 (indicating an error due to malformed output or exceeding the query limit), your program must terminate immediately to avoid unexpected verdicts.

? 3 9

49

? 1 1

0

? 5 5

1

! 000110101110111100101100...