题目背景

「Yes, I am Q.」

面前的小 R 莞尔一笑。

• 保证本题的任何合理的部分分或正解的 std + spj 均可以在当前数据下，$900$ ms 的时间限制、$32$ MB 的空间限制内正确运行并获得 AC 状态。
• 本题不添加仅为无意义地卡满 spj 运行时间的 hack 数据。

请注意，本题只有约束范围与普通版不同，且两个版本的约束范围并不完全重叠。

题目描述

这是一道交互题。

小 R 有一个变量 $Q$。$Q$ 初始为 $0$。

小 R 有 $n$ 个隐藏的整数 $q_1 \dots q_n$，满足 $1 \leq \lvert q_i \rvert \leq V$，且有且仅有一个 $i$ 满足 $q_i \lt 0$，而面前的你，需要得出这个满足 $q_i \lt 0$ 的下标 $i$。

小 R 承诺不会让你以仅仅 $\frac{1}{n}$ 的几率盲猜，所以她可以允许你进行最多 $k$ 次询问。每次询问，你可以向小 R 给出可重正整数集合 $S$ 满足 $0 \leq \lvert S \rvert \leq S_{\max}$ 且 $\forall i \in S, i \leq n$，她会计算 $M = \prod\limits_{i\in S}q_i$，然后让 $Q \leftarrow Q + M$。特殊地，若 $S$ 为空集，则 $M = 1$。

一次询问后，小 R 会向你给出此时的 $\text{sgn}(Q)$（为 +，- 或 0），表示 $Q$ 的符号。具体地，若 $Q \gt 0$，小 R 返回 +；若 $Q \lt 0$，小 R 返回 -；否则返回 0。

请你在不超过 $k$ 次询问后，找到那个满足 $q_i \lt 0$ 的下标 $i$。

保证对于所有数据，满足 $q_i \lt 0$ 的下标 $i$ 是在 $[1, n]$ 内均匀随机选取的。请注意报告下标属于一次询问。

输入格式

交互格式

第一行，输入三个正整数 $n, k, S_{\max}$。

在此之后，你应当进行若干次询问。

对于你的每组询问，输出 $?\ m\ s_1\ s_2 \dots s_m$，表示给出一个可重正整数集合 $S$，其大小为 $m$，你需要保证 $0 \leq m \leq S_{\max}$。此外，同时应有 $1 \leq s_i \leq n$，描述这个集合里的元素编号。

如果你已经得到答案，请输出 $!\ i$，满足 $1 \leq i \leq n$，代表你得到 $q_i \lt 0$，在这之后你应当立即退出本轮交互。

每次你输出之后，请刷新缓冲区。

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

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

每次询问并刷新缓冲区后，你将从标准输入中输入一个字符，字符为 +，- 或 0，表示当前 $Q$ 的符号 $\text{sgn}(Q)$。

输入格式

本题有多组数据。

第一行，一个整数 $T$ 表示数据组数。

对于每一组数据，请按照 【交互格式】 进行交互。当你报告下标后：

• 如果你给出的下标正确：
  • 如果这是最后一组数据，交互库退出并返回 Accepted；
  • 如果这不是最后一组数据，你应当接着读入 $n, k, S_{\max}$ 以进行下一组数据的交互。
• 否则，下标错误，交互库会立刻终止，返回 Unaccepted。

输出格式

见 【输入格式】。

1
6 6 6

-

-

-

+

0

? 1 1

? 5 1 2 3 4 5

? 3 2 4 6

? 1 4

? 3 1 5 6

! 1

提示

样例解释 1

$q = \{-1, 1, 4, 5, 1, 4\}$。

数据规模与约定

本题采用捆绑测试。

子任务编号	$n \leq$	$T \leq$	$k =$	$S_{\max} =$	分值
$0$	$200$	$500$	$20$	$20n + 1$	$11$
$1$	$1000$	$50$	$41$	$8n + 10$	$25$
$2$			$50$	$6n + 10$	$30$
$3$	$10^4$	$10$	$39$	$\lceil 1.5n\rceil + 10$	$34$

对于子任务 $0, 1, 3$，若通过所有测试点则获得全部分数，否则获得 $0$ 分。

对于子任务 $2$：

• 你需要保证你所使用的实际操作次数 $k'$ 满足 $0 \leq k' \leq 50$。
• 你需要保证你所使用的实际操作次数 $S'$ 满足 $0 \leq S' \leq 6n + 10$。
• 单个测试点的得分为 $\left(1 - \max(\frac{\max k' - 35}{20}, \max(\frac{S' - 3n - 10}{4n + 1}), 0)\right)\times 30$。
• Subtask 的得分取所有测试点的得分最小值。

对于所有数据，$1 \leq V \leq 10^6$，$1 \leq n \leq 10^4$，$1 \leq T \leq 500$，注意由于交互库限制 $\bm{n, T}$ 不会同时取到最大值；此外，对每个子任务 $k, S_{\max}$ 的值已经给出。