P9916 “RiOI-03” Just a Q. (Easy ver.)

“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.**

**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.**

## 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

See **[Input Format]**.

## 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