Background

"Yes, I am Q."

Little R smiles slightly.

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

Note that only the Constraints differ from the normal version, 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 find this index $i$ with $q_i \lt 0$.

Little R promises she will not make you blindly guess with only a $\frac{1}{n}$ chance, 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$, and then update $Q \leftarrow Q + M$. In particular, if $S$ is empty, then $M = 1$.

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

You must find the index $i$ with $q_i \lt 0$ using no more than $k$ queries.

It is guaranteed that for all testdata, the index $i$ such that $q_i \lt 0$ is chosen uniformly at random from $[1, n]$. Note that reporting an index counts as one query.

Input Format

Interactive format

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

After that, you should make some 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 multiset.

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

After each output, 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 documentation of the corresponding language.

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

After each query and flushing the buffer, you will read one character from standard input, which is +, -, or 0, representing the current sign $\text{sgn}(Q)$.

Input format

This problem has multiple test cases.

The first line contains an integer $T$, indicating the number of test cases.

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

• If the index you give is correct:
  • If this is the last test case, the interactor exits and returns Accepted.
  • If this is not the last test case, you should continue to read $n, k, S_{\max}$ to start interacting for the next test case.
• Otherwise, if the index is incorrect, the interactor 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\}$.

Constraints and conventions

This problem uses bundled tests.

For subtasks $0, 1, 3$, if you pass all test points you get the full score; otherwise you get $0$ points.

For subtask $2$:

• You need to ensure that the actual number of operations you use, $k'$, satisfies $0 \leq k' \leq 50$.
• You need to ensure that the actual number of operations you use, $S'$, satisfies $0 \leq S' \leq 6n + 10$.
• The score for a single test point is $\left(1 - \max(\frac{\max k' - 35}{20}, \max(\frac{S' - 3n - 10}{4n + 1}), 0)\right)\times 30$.
• The subtask score is the minimum score among all test points.

For all testdata, $1 \leq V \leq 10^6$, $1 \leq n \leq 10^4$, $1 \leq T \leq 500$. Note that due to interactor limitations, $\bm{n, T}$ will not both take their maximum values at the same time. Also, the values of $k$ and $S_{\max}$ for each subtask are already given.

Translated by ChatGPT 5