P7837 “Wdoi-3” Night Sparrow Cooking

As the chef of Gensokyo, Mystia can of course use the prepared ingredients to make all kinds of dishes. At night, the Night Sparrow Restaurant opens for business. With these dishes, the restaurant is always thriving—some “special customers” even come to visit. Special customers are some characters that everyone in Gensokyo knows well. As the name suggests, they will make special requests, but if you satisfy their requests, they will reward little Night Sparrow properly. Unfortunately, Yukari decided to play a prank. She secretly used her ability to erase part of Mystia’s memory, and now Mystia cannot tell which customers are special and which are ordinary! Seeing Mystia about to cry, Yukari, feeling sorry for her, decided to play a math game with Mystia. She hid the IDs of the special customers inside numbers. Mystia knows nothing about math, so she can only ask you for help.

**This is an interactive problem.** Yukari provides a sequence of length $n$, where the $i$-th term corresponds to the customer with ID $i$. She colors all positions corresponding to ordinary customers blue, and positions corresponding to special customers purple. Yukari tells Mystia that there are $m$ special customers in total. Also, since special customers are very special, the number of purple positions is small and **roughly uniformly random**. Next, she assigns a value to each term of the sequence. The value $a_i$ of the $i$-th term can be derived by the following formula (Yukari will provide both $s$ and $k$): $$a_i=\begin{cases} s & i=1\cr a_{i-1}+k & i>1\end{cases}$$ Mystia may ask Yukari queries of the form `l r`, and Yukari will quickly compute the sum of $a_i$ over all blue positions within the interval $[l,r]$. Of course, you need to output `l r` to tell Mystia how to ask. If you successfully find all special customer IDs (i.e. all purple positions), you need to output `-1 p1 p2 ... pm` to tell Mystia all special customer IDs. Note that you must ensure $p_i\le p_{i+1}(1\le i

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. Then each test case follows. First, Night Sparrow will convey the information Yukari said, i.e. the values of $n,m,s,k$. Then you may initiate several queries until you tell Mystia all special customer IDs. At this point, the test case ends and the next one begins.

Output several lines. You may initiate queries to standard output to get Mystia’s responses. **Note:** If something goes wrong during your queries (including but not limited to too many queries, out-of-range queries, etc.), Mystia will tell you `-1` (meaning Yukari does not want to pay attention to her anymore). In this case, you should stop immediately, otherwise strange situations may occur.

#### Sample Explanation The mysterious customers have IDs $\{4,7,10,11\}$. This sample symbolically uses $3$ queries to help contestants understand the interactive process. - For the first query $[10,12]$, the result is $13=13$. - For the second query $[2,7]$, the result is $3+4+6+7=20$. - For the third query $[4,8]$, the result is $6+7+9=22$. --- #### Constraints and Conventions $$\def\arraystretch{1.8} \begin{array}{|c|c|c|}\hline \textbf{Subtask} & \textbf{Special Property} & \textbf{Score} \cr\hline 1 & m=1 & 5 \cr\hline 2 & - & 95 \cr\hline \end{array}$$ - For all testdata, it holds that $1\le T\le 500$, $1 \leq \sum n_i \leq 10^5$, $1 \leq \sum m_i \leq \min\{ n,100\}$, and $1\le s,k\le 10^9$. The score of each Subtask is the lowest score among all test points in the current Subtask. #### Scoring Method Let $q_i$ be the number of queries you use for the $i$-th test case. You must satisfy $\sum q_i \leq 200 \times T$, and every query result must be correct, to get full score for that test point. - If the number of queries satisfies $1000 \times T> 11, x ^= (x 18; idx = (idx + 1) % 624; return x; } u32 clc(u32 n){ //uniformly randomly return an integer in [0,n) return 1ull * n * clc() >> 32; } void sfl(int n, int *A) { for(int i = n;i >= 1; --i) swap(A[clc(i) + 1], A[i]); } void gen(u32 seed,int n, int *A) { iit(seed); for(int i = 1;i