Background

“Yes, I am Q.”

Little R smiled.

• It is guaranteed that any reasonable partial solution or full solution with std + spj for this problem can run correctly and get AC under the current testdata within the time limit of $400$ ms and the memory limit of $32$ MB.
• This problem does not add hack testdata that is only meant to meaninglessly max out the spj running time.

Please note that this problem differs from the hard version only in the constraints, and the constraints of the two versions do not completely overlap.

Problem Description

This is an interactive problem.

Little R has a variable $Q$. Initially, $Q = 0$.

Little R has $n$ hidden integers $q_1 \dots q_n$, satisfying $1 \leq \lvert q_i \rvert \leq V$, and there exists exactly one index $i$ such that $q_i \lt 0$. You need to determine this index $i$ with $q_i \lt 0$.

Little R promises she will not make you blindly guess with only probability $\frac{1}{n}$, so she allows you to make at most $k$ queries. In each query, you may give Little R a multiset $S$ of positive integers satisfying $0 \leq \lvert S \rvert \leq S_{\max}$ and $\forall i \in S, i \leq n$. She will compute $M = \prod\limits_{i\in S} q_i$, then update $Q \leftarrow Q + M$. In particular, if $S$ is empty, then $M = 1$.

After one query, Little R will tell you the current $\text{sgn}(Q)$ (which is +, -, or 0), i.e., the sign of $Q$. Specifically, if $Q \gt 0$, she returns +; if $Q \lt 0$, she returns -; otherwise she returns 0.

You must find the index $i$ such that $q_i \lt 0$ within at most $k$ queries.

It is guaranteed that for all testdata, the index $i$ with $q_i \lt 0$ is chosen uniformly at random in $[1, n]$. Please note that reporting the index counts as one query.

Input Format

Interactive Protocol

In the first line, read three positive integers $n, k, S_{\max}$.

After that, you should perform several queries.

For each query, output ?\ m\ s_1\ s_2 \dots s_m, meaning you provide a multiset $S$ of positive integers of size $m$. You must ensure $0 \leq m \leq S_{\max}$. Also, you must have $1 \leq s_i \leq n$, describing the indices of the elements in the set.

If you have obtained the answer, output !\ i with $1 \leq i \leq n$, meaning you conclude $q_i \lt 0$. After that, you should immediately exit the current interaction round.

After each output, you must flush the buffer.

You may use the following statements to flush the buffer:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);
• For other languages, please check the help documentation for your language.

In particular, for C++, if you use std::endl instead of '\n' when printing a newline, it will also flush the buffer automatically.

Each time after you query and flush the buffer, you will read one character from standard input: +, -, or 0, representing the current sign $\text{sgn}(Q)$.

Input Format

This problem contains multiple test cases.

In the first line, an integer $T$ indicates the number of test cases.

For each test case, interact according to [Interactive Protocol]. After you report an index:

• If the index you give is correct:
  • If this is the last test case, the interactive library exits and returns Accepted.
  • If this is not the last test case, you should continue by reading $n, k, S_{\max}$ to start interacting for the next test case.
• Otherwise, if the index is wrong, the interactive library will terminate immediately and return Unaccepted.

Output Format

See [Input Format].

1
6 6 6

-

-

-

+

0

? 1 1

? 5 1 2 3 4 5

? 3 2 4 6

? 1 4

? 3 1 5 6

! 1

Hint

Sample Explanation 1

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

Data Scale and Constraints

This problem uses bundled tests.

• Subtask 0 (5 pts): $q_i \neq 1$ and $q_i \neq -1$.
• Subtask 1 (10 pts): $q_i \neq -1$, $k = 2n$.
• Subtask 2 (10 pts): $q_i \neq 1$, $k = 2n$.
• Subtask 3 (9 pts): $n = 13$, $k = 5000$.
• Subtask 4 (11 pts): $n = 13$, $k = 2500$.
• Subtask 5 (20 pts): $k = 2n$.
• Subtask 6 (35 pts): No additional constraints.

For each test case, $1 \leq n \leq 200$, $1 \leq V \leq 10^6$, $n \leq k \leq 5\times 10^3$, and $S_{\max} = n$.

For each test point, $1 \leq T \leq 500$, $\sum n^2 \leq 2\times 10^5$, and $\sum k \leq 2\times 10^5$.

Translated by ChatGPT 5