[AdditionalFile3065.zip](file://AdditionalFile3065.zip?type=additional_file)

#3065. 「ROI 2016 Day2」DNA 解码

标签: 交互 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

译自 ROI 2016 Day2 T2. Расшифровка ДНК

某古生物的 DNA 是一条包含 $n$ 个脱氧核苷酸的序列，但是该生物的 DNA 中核苷酸的种类可能与现代生物不同。

某种机器可以扫描 DNA 中连续的一段，并给出该段中包含多少种核苷酸。然而你只能使用这种机器至多 $q$ 次。

试求出该 DNA 中包含多少种核苷酸（假设包含 $k$ 种）。此外，你还需要给这 $k$ 种核苷酸编号（比如 GMP→1，AMP→2），然后给出用编号形式表示的完整 DNA 序列（比如 ATGC->2314）。请注意，你给出的 DNA 序列可以与标准答案中的不同，你只需保证：同种核苷酸使用编号相同，且不同种核苷酸编号不同。

交互方式

本题使用标准输入输出进行交互。

首先，你的程序可以从 stdin 读取一个整数 $n$。

你可以通过输出 "$\;\!\texttt{?}\ i\ j\;\!$" 来查询 DNA 的第 $i\sim j$ 个核苷酸中有多少种不同的核苷酸。交互器在接收到你的查询后，会在 stdin 中给出答复。

如果你得出了答案，请输出 Ready!，下一行输出 $k$，再下一行输出 $n$ 个整数，表示 DNA 序列。

你需要在输出你要执行的命令后刷新 stdout 的缓冲区来将命令发送到交互器。

• 如果你使用 C++ 且使用 iostream 系列，可以输出 std::flush 或 std::endl 来刷新缓冲区。
• 如果你使用 C/C++ 且使用 cstdio，那么请调用标准库函数 fflush(stdout) 来刷新。
• 如果你使用 Python，请使用 sys.stdout.flush()。
• 如果你使用 Java，请使用 System.out.flush() 。

样例

输入

123

输出

123

$$\begin{array}{l|l} \hline \rm stdin &\rm stdout\\ \hline \tt 2 & \\ &\tt ?\ 1\ 2 \\ \tt 2 & \\ &\tt Ready!\\ &\tt 2\\ &\tt 1\ 2\\ \hline \end{array}$$

2
2

? 1 2
Ready!
2
1 2

$$\begin{array}{l|l} \hline \rm stdin &\rm stdout\\ \hline \tt 3 & \\ &\tt ?\ 1\ 2 \\ \tt 1 & \\ &\tt ?\ 1\ 3 \\ \tt 2 & \\ &\tt Ready!\\ &\tt 2\\ &\tt 1\ 1\ 2\\ \hline \end{array}$$

3
1
2

? 1 2
? 1 3
Ready!
2
1 1 2

数据范围与提示

子任务 #	分值	$1⩽ n ⩽$	$1 ⩽ k ⩽$	$q=$
1	20	$300$	$2$	$72000$
2	25		$n$
3	25	$3000$	$10$
4	15		$n$
5	15			$36000$