Type: Interactive 4000ms 1024MiB

[2026 CCPC_NC_I E] 猜01序列

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

这是一道交互题。

给定正整数 nn,评测机会生成一个未知的长度为 nn 的 01\texttt{01} 序列 a1,a2,…,ana_1,a_2,\ldots,a_n,你最多可以询问评测机 1717 个问题,来求解这个 01\texttt{01} 序列中 1\texttt{1} 的个数,即 ∑i=1nai\sum_{i=1}^{n} a_i。数据保证至少有一个 1\texttt{1}。

对于每一次询问,你可以选择若干个位置 i1,i2,…,iki_1,i_2,\ldots,i_k,设 I={i1,i2,…,ik}I=\{i_1,i_2,\ldots,i_k\},评测机会返回 (∑j∈Iaj)⋅(∑j∉Iaj)(\sum_{j\in I} a_j)\cdot(\sum_{j\notin I} a_j) 的结果。

Input

第一行一个正整数 n(1≤n≤105)n (1 \le n \le 10^5 ),表示这个 0101 序列的长度。

Interaction

对于询问,请按以下格式输出一行(不包括引号):

``? kk i1i_1 i2i_2 …\ldots iki_k'' (1≤k≤n1\le k\le n, 1≤i1<i2<⋯<ik≤n1\le i_1<i_2<\cdots<i_k\le n)。

对于输出答案,请按以下格式输出一行(不包括引号):

``! ss'',其中 s=∑i=1nais=\sum_{i=1}^{n} a_i。

输出答案本身不计入查询次数。

交互器是非自适应的,也就是说,答案在参与者提出任何查询之前就已经确定了,并且不会依赖于参与者所提出的查询。

在输出每个查询之后,不要忘记输出换行并刷新输出缓冲区。

你可以使用如下语句来清空缓冲区:

  • 对于 C/C++:fflush(stdout)\texttt{fflush(stdout)}
  • 对于 C++:std::cout << std::flush\texttt{std::cout << std::flush}
  • 对于 Java:System.out.flush()\texttt{System.out.flush()}
  • 对于 Python:sys.stdout.flush()\texttt{sys.stdout.flush()}

Samples

3

2

? 2 1 3

! 3
3

0

0

? 1 1

? 1 2

! 1

Note

第一个样例隐藏的数列为 [1,1,1][1, 1, 1],第二个样例隐藏的数列为 [0,1,0][0, 1, 0]。