Description

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<m)$.

Note: After performing either of these two operations, you must flush the output buffer. Below are some common ways to flush the buffer in popular languages:

• C++: fflush(stdout) or cout.flush().
• C: fflush(stdout).
• Java: System.out.flush().
• Python: stdout.flush().
• Pascal: flush(output).
• Other languages: please refer to the documentation of the corresponding language.

Input Format

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 Format

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.

1
12 4 2 1

13

20

22

10 12

2 7

4 8

-1 4 7 10 11

Hint

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<\sum q_i \leq 2000 \times T$, you can get $20\%$ of the score.
• If the number of queries satisfies $600 \times T<\sum q_i \leq 1000 \times T$, you can get $40\%$ of the score.
• If the number of queries satisfies $400 \times T<\sum q_i \leq 600 \times T$, you can get $50\%$ of the score.
• If the number of queries satisfies $300 \times T<\sum q_i \leq 400 \times T$, you can get $60\%$ of the score.
• If the number of queries satisfies $200 \times T<\sum q_i \leq 300 \times T$, you can get $80\%$ of the score.

Notes

The way to generate $m$ purple points is: apply random_shuffle to a permutation of $1 \sim n$, then take the first $m$ values as the special customer IDs. A reference implementation is as follows:

namespace Gen{
	typedef unsigned int       u32;
	typedef unsigned long long u64;
	u32 MT[624],idx;
	void iit(u32 seed){
    	MT[0]=seed; idx=0; for(u32 i = 1;i < 624;++ i)
    	MT[i]=(0x6c078965U * (MT[i - 1] ^ ((MT[i - 1]) >> 30)) + i);
	}
	void gen(){
		u32 x; for(u32 i = 0;i < 624; ++ i){
			x = (MT[i] & 0x80000000U) +
				(MT[(i + 1) % 624] & 0x7fffffffU );
			MT[i] = MT[(i + 397) % 624] ^ (x >> 1);
			if(x & 1) MT[i] ^= 0x9908b0dfU;
		}
	}
	u32  clc(){
		if(!idx) gen(); u32 x = MT[idx];
		x ^= x >> 11, x ^= (x << 7) & 0x9d2c5680U;
		x ^= (x << 15) & 0xefc60000U,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 <= n; ++i) A[i] = i; sfl(n, A);
	}
}

Note: This code snippet uses a standard-compliant Mersenne Twister algorithm to generate random numbers. Its period is $2^{19937}-1$, and the generated random numbers are uniformly random. Therefore, you do not need to worry that we did any tricks in it.

Calling gen(seed,n,A) generates a length $n$ sequence that is roughly uniformly random. We will take its first $m$ elements as the special customer IDs. For example, in the sample, we called gen(9961U,12,A) and selected the first $4$ elements of $A$, $\{4,7,10,11\}$, as the mysterious customer IDs.

Translated by ChatGPT 5