P9918 "RiOI-03" Just a Q. (Hard ver.)

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

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

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

See **[Input Format]**.

### Sample explanation 1 $q = \{-1, 1, 4, 5, 1, 4\}$. ### Constraints and conventions **This problem uses bundled tests.** | Subtask ID | $n \leq$ | $T \leq$ | $k = $ | $S_{\max} = $ | Score | | :-: | :-: | :-: | :-: | :-: | :-: | | $0$ | $200$ | $500$ | $20$ | $20n + 1$ | $11$ | | $1$ | $1000$ | $50$ | $41$ | $8n + 10$ | $25$ | | $2$ | $1000$ | $50$ | $50$ | $6n + 10$ | $30$ | | $3$ | $10^4$ | $10$ | $39$ | $\lceil 1.5n\rceil + 10$ | $34$ | 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