CF1081F.Tricky Interactor

This is an interactive problem.

Chouti was tired of studying, so he opened the computer and started playing a puzzle game.

Long long ago, the boy found a sequence $s_1, s_2, \ldots, s_n$ of length $n$, kept by a tricky interactor. It consisted of $0$s and $1$s only and the number of $1$s is $t$. The boy knows nothing about this sequence except $n$ and $t$, but he can try to find it out with some queries with the interactor.

We define an operation called flipping. Flipping $[l,r]$ ($1 \leq l \leq r \leq n$) means for each $x \in [l,r]$, changing $s_x$ to $1-s_x$.

In each query, the boy can give the interactor two integers $l,r$ satisfying $1 \leq l \leq r \leq n$ and the interactor will either flip $[1,r]$ or $[l,n]$ (both outcomes have the same probability and all decisions made by interactor are independent from each other, see Notes section for more details). The interactor will tell the current number of $1$s after each operation. Note, that the sequence won't be restored after each operation.

Help the boy to find the original sequence in no more than $10000$ interactions.

"Weird legend, dumb game." he thought. However, after several tries, he is still stuck with it. Can you help him beat this game?

Interaction

The interaction starts with a line containing two integers $n$ and $t$ ($1 \leq n \leq 300$, $0 \leq t \leq n$) — the length of the sequence and the number of $1$s in it.

After that, you can make queries.

To make a query, print a line "? l r" ($1 \leq l \leq r \leq n$), then flush the output.

After each query, read a single integer $t$ ($-1 \leq t \leq n$).

• If $t=-1$, it means that you're out of queries, you should terminate your program immediately, then you will get Wrong Answer, otherwise the judging result would be undefined because you will interact with a closed stream.
• If $t \geq 0$, it represents the current number of $1$s in the sequence.

When you found the original sequence, print a line "! s", flush the output and terminate. Print $s_1, s_2, \ldots, s_n$ as a binary string and do not print spaces in between.

Your solution will get Idleness Limit Exceeded if you don't print anything or forget to flush the output.

To flush you need to do the following right after printing a query and a line end:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks

For hacks, use the following format:

In the first and only line, print a non-empty binary string. Its length will be $n$ and it will be treated as $s_1, s_2, \ldots, s_n$.

For example, the the test corresponding to the example contains a line "0011".

这是一个交互式问题。

Chouti 学习学累了，于是打开电脑开始玩一个谜题游戏。

很久以前，这个男孩发现了一个长度为 $n$ 的序列 $s_1, s_2, \ldots, s_n$，它被一个狡猾的交互器（interactor）所保管。该序列仅由 $0$ 和 $1$ 构成，其中 $1$ 的个数恰好为 $t$。男孩除了知道 $n$ 和 $t$ 之外，对该序列一无所知，但他可以通过向交互器发起若干查询来尝试还原它。

我们定义一种称为“翻转”（flipping）的操作：翻转区间 $[l,r]$（其中 $1 \leq l \leq r \leq n$）表示对每个 $x \in [l,r]$，将 $s_x$ 变为 $1 - s_x$。

在每次查询中，男孩可以向交互器提供两个整数 $l, r$（满足 $1 \leq l \leq r \leq n$），交互器将以相等的概率随机选择执行以下两种操作之一：翻转 $[1,r]$ 或翻转 $[l,n]$（交互器的所有决策相互独立；更多细节请参见“注意事项”部分）。交互器将在每次操作后返回当前序列中 $1$ 的个数。注意：每次操作后序列不会恢复原状。

请帮助男孩在不超过 $10000$ 次交互内还原原始序列。

“离谱的传说，愚蠢的游戏。”他心想。然而，尝试了几次后，他依然卡在这个游戏里。你能帮他通关吗？

交互方式

交互以一行包含两个整数 $n$ 和 $t$（$1 \leq n \leq 300$，$0 \leq t \leq n$）开始——分别表示序列长度和其中 $1$ 的个数。

之后，你可以发起查询。

要发起一次查询，请输出一行 "? l r"（其中 $1 \leq l \leq r \leq n$），然后刷新输出缓冲区（flush）。

每次查询后，读入一个整数 $t$（$-1 \leq t \leq n$）：

• 若 $t = -1$，表示你已超出查询次数限制，此时你必须立即终止程序；否则你会得到“Wrong Answer”，因为后续将与已关闭的流进行交互，评测结果将未定义。
• 若 $t \geq 0$，则表示当前序列中 $1$ 的个数。

当你确定了原始序列，请输出一行 "! s"，刷新输出并终止程序。其中 $s$ 是一个长度为 $n$ 的二进制字符串，即 $s_1 s_2 \ldots s_n$，中间不要加空格。

若你不输出任何内容或忘记刷新输出，你的程序将收到 “Idleness Limit Exceeded”。

刷新输出的方法（在输出查询及换行符后立即执行）如下：

• C++ 中：fflush(stdout) 或 cout.flush()；
• Java 中：System.out.flush()；
• Pascal 中：flush(output)；
• Python 中：stdout.flush()；
• 其他语言请查阅相应文档。

Hack（自定义测试用例）

对于 hack，请使用如下格式：

在唯一的一行中，输入一个非空的二进制字符串。其长度即为 $n$，并将被视作 $s_1, s_2, \ldots, s_n$。

例如，对应样例的测试用例包含一行 "0011"。

For first query $1,1$, the interactor should flip $[1,1]$ or $[1,4]$. It chose to flip $[1,4]$, so the sequence became 1100.

For second query $1,1$, the interactor should flip $[1,1]$ or $[1,4]$. It again chose to flip $[1,4]$, so the sequence became 0011.

For third query $3,4$, the interactor should flip $[1,4]$ or $[3,4]$. It chose to flip $[3,4]$, so the sequence became 0000.

Q: How does interactor choose between $[1,r]$ and $[l,n]$? Is it really random?

A: The interactor will use a secret pseudorandom number generator. Only $s$ and your queries will be hashed and used as the seed. So if you give the same sequence of queries twice for the same secret string, you will get the same results. Except this, you can consider the choices fully random, like flipping a fair coin. You needn't (and shouldn't) exploit the exact generator to pass this problem.

对于第一次查询 $1,1$，交互器应当翻转区间 $[1,1]$ 或 $[1,4]$。它选择翻转 $[1,4]$，因此序列变为 1100。

对于第二次查询 $1,1$，交互器应当翻转区间 $[1,1]$ 或 $[1,4]$。它再次选择翻转 $[1,4]$，因此序列变为 0011。

对于第三次查询 $3,4$，交互器应当翻转区间 $[1,4]$ 或 $[3,4]$。它选择翻转 $[3,4]$，因此序列变为 0000。

问：交互器如何在 $[1,r]$ 和 $[l,n]$ 之间做出选择？这真的是随机的吗？

答：交互器将使用一个秘密的伪随机数生成器。仅将秘密字符串 $s$ 和你的所有查询拼接后进行哈希，并以此哈希值作为该伪随机数生成器的种子。因此，若对同一秘密字符串 $s$ 以完全相同的查询序列运行两次，则会得到完全相同的结果。除此之外，你可以将这些选择视为完全随机（例如抛一枚均匀硬币）。你无需（也不应）利用该伪随机数生成器的具体实现细节来通过本题。