这是一个交互式问题，你的程序将通过标准输入和标准输出与评测系统进行交互。

给定整数 $N, K$ 和 $Q$。评测系统持有一个 $(1, 2, \dots, N)$ 的隐藏排列 $(a_1, a_2, \dots, a_N)$。你可以向评测系统发起最多 $Q$ 次查询，每次查询如下：

• 选择一个子集 $S \subseteq \{1, 2, \dots, N\}$。评测系统将返回满足 $i < j$ 且 $|a_i - a_j| \le K$ 的不同下标对 $(i, j)$ 的数量，其中 $i, j \in S$。

令 $x$ 为满足 $a_t = 1$ 的下标 $t$，令 $y$ 为满足 $a_t = N$ 的下标 $t$。你的任务是确定集合 $\{x, y\}$。（你不需要区分哪个是 $x$，哪个是 $y$。）

评测系统是非自适应的，这意味着排列 $(a_1, a_2, \dots, a_N)$ 在任何交互开始前就已经固定。

输入格式

• 所有输入值均为整数。
• $N = 20000$
• $1 \le K \le 10$
• $Q = 30(K + 1)$

交互

首先，从标准输入读取整数 $N, K$ 和 $Q$：

$N \ K \ Q$

然后，重复以下过程，直到你确定了集合 $\{x, y\}$：

对于一次查询，向标准输出按以下格式输出：

$? \ s_1s_2 \dots s_N$

其中 $s_1s_2 \dots s_N$ 是一个长度为 $N$ 的二进制字符串，表示子集 $S$。若 $i \in S$，则 $s_i = 1$，否则 $s_i = 0$。

查询的响应将通过标准输入提供，格式如下：

$T$

其中 $T$ 是查询的答案，表示满足 $i < j$ 且 $|a_i - a_j| \le K$ 的不同下标对 $(i, j)$ 的数量，其中 $i, j \in S$。

当你确定了集合 $\{x, y\}$ 后，按以下格式输出这两个元素（顺序无关紧要）并立即终止程序：

$! \ x \ y$

说明

• 在每次输出消息后，请打印换行符并刷新标准输出。否则，你可能会收到“超出时间限制”（Time Limit Exceeded）的判决。
• 如果你的查询格式无效或查询次数超过限制，评测系统将返回 $T = -1$。如果你收到此响应，应立即终止程序。否则，你可能会收到“超出时间限制”的判决。
• 注意，不必要的换行符会被视为格式错误。

样例

以下是 $N = 5, K = 2, Q = 90$ 的交互示例。注意，此示例不满足题目给出的数据范围，且不会出现在测试用例中。

样例输入 1

5 2 90
1
2

样例输出 1

? 11000
? 10011
! 2 4

说明 1