「Wdoi-3」夜雀 cooking

**本题为交互题。** 作为幻想乡的大厨，米斯蒂娅当然能用准备的食材制作出各色各样的饭菜。晚上，就是夜雀餐厅营业的时间，凭着这些料理，餐厅总是生意兴隆——甚至一些「特殊顾客」也会前来！ 特殊顾客就是一些幻想乡里大家再熟悉不过的角色啦，顾名思义，她们会提出特殊要求，不过如果满足了她们的要求，她们也会好好地奖励小夜雀。 不幸的是，紫决定做一个恶作剧，她悄悄使用能力清除了米斯蒂娅的部分记忆，现在她分不清哪些顾客是特殊顾客，哪些顾客是普通顾客了！看着米斯蒂娅快要哭了，于心不忍的紫决定和米斯蒂娅做一个数学游戏，她将特殊顾客的编号隐藏在了数字之中。米斯蒂娅对数学一窍不通，于是她只能向你求助了......

紫给出了一个长度为 $n$ 的数列，其第 $i$ 项就对应了编号为 $i$ 的顾客。她将所有普通顾客对应的位置染上蓝色，把特殊顾客对应的位置染上紫色。紫告诉了米斯蒂娅特殊顾客一共有 $m$ 位。并且，由于特殊顾客非常的特殊，所以紫色位置数量很少，而且**基本均匀随机**。 接下来，她给数列的每一项赋上了值。第 $i$ 项的值 $a_i$ 可以用如下的式子推出：（$s$ 和 $k$ 紫都会给出） $$a_i=\begin{cases} s & i=1\cr a_{i-1}+k & i>1\end{cases}$$ 米斯蒂娅可以向紫提出形如 `l r` 的问题，然后紫就会迅速算出区间 $[l,r]$ 内所有被染成蓝色位置的 $a_i$ 的和。当然啦，你需要输出 `l r` 来告诉米斯蒂娅她该如何提问，如果你成功找出了所有特殊顾客的编号（即所有紫色点的位置），那么你需要输出 `-1 p1 p2 ... pm` 来告诉米斯蒂娅所有特殊顾客的编号，注意要保证 $p_i\le p_{i+1}(1\le i<m)$。 **注意：在进行这两种操作后，需要刷新缓存区，下面是一些常见语言的刷新缓存区方式：** - C++：`fflush(stdout)` 或 `cout.flush()`。 - C: `fflush(stdout)`。 - Java: `System.out.flush()`。 - Python: `stdout.flush()`。 - Pascal: `flush(output)`。 - 其他语言：请参考对应语言的帮助文档。

**本题有多组数据。** 第一行是一个正整数 $T$，表示数据组数。 接下来进行每组数据。首先夜雀会传达紫所说的信息，也就是 $n,m,s,k$ 的值，接着你可以发起若干次询问，直到你告诉了米斯蒂娅所有特殊顾客的编号。此时该组数据结束，进入到下一组。

输出若干行。你可以向标准输出中发起询问来得到米斯蒂娅的回答。 **注意：** 如果你在询问过程中出了问题（包括但不限于询问次数过多，询问越界等），此时米斯蒂娅会告诉你 $-1$（代表紫不想理她了）。此时你应立即停止，否则可能会出现奇怪的状况。

1
12 4 2 1

13

20

22

10 12

2 7

4 8

-1 4 7 10 11

#### 样例解释 神秘顾客的编号为 $\{4,7,10,11\}$ 。这个样例象征性地抽取了 $3$ 个询问，以便选手理解交互的过程。 - 对于第一次询问 $[10,12]$ ，结果为 $13=13$。 - 对于第二次询问 $[2,7]$ ，结果为 $3+4+6+7=20$。 - 对于第三次询问 $[4,8]$ ，结果为 $6+7+9=22$。 --- #### 数据范围及约定 $$\def{\arraystretch}{1.8} \begin{array}{|c|c|c|}\hline \textbf{Subtask} & \textbf{特殊性质} & \textbf{分值} \cr\hline 1 & m=1 & 5 \cr\hline 2 & - & 95 \cr\hline \end{array}$$ - 对于所有数据，满足 $1\le T\le 500$，$1 \leq \sum n_i \leq 10^5$，$1 \leq \sum m_i \leq \min\{ n,100\}$，$1\le s,k\le 10^9$。 每一个 Subtask 的得分为当前 Subtask 所有测试点的最低分。 #### 判分方式 令 $q_i$ 为对于第 $i$ 组数据你所用的询问次数，你需要满足 $\sum q_i \leq 200 \times T$ ，并且每组询问的结果都是正确的，你才能获得该测试点的满分。 - 如果询问次数满足 $1000 \times T<\sum q_i \leq 2000 \times T$，可以拿到 $20\%$ 的分数。 - 如果询问次数满足 $600 \times T<\sum q_i \leq 1000 \times T$，可以拿到 $40\%$ 的分数。 - 如果询问次数满足 $400 \times T<\sum q_i \leq 600 \times T$，可以拿到 $50\%$ 的分数。 - 如果询问次数满足 $300 \times T<\sum q_i \leq 400 \times T$，可以拿到 $60\%$ 的分数。 - 如果询问次数满足 $200 \times T<\sum q_i \leq 300 \times T$，可以拿到 $80\%$ 的分数。 #### 说明 选择 $m$ 个点染为紫色的生成方式是对一个 $1 \sim n$ 的排列调用 `random_shuffle`，然后取前 $m$ 项的数值作为特殊顾客的编号。一个可被参考的代码如下： ```cpp 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){ //均匀随机地返回 [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); } } ``` **注**：该代码片段会使用符合标准的梅森旋转算法生成随机数。其生成随机数的周期为 $2^{19937}-1$ ，生成的随机数是均匀随机的。因此你大可不必担心我们在里面做了任何手脚。 调用 `gen(seed,n,A)` 可以生成一个长度为 $n$ 的**基本均匀随机**序列，我们将会取其前 $m$ 项作为特殊顾客的编号。例如，对于样例，我们调用了 `gen(9961U,12,A)` ，并选取了 $A$ 的前 $4$ 项 $\{4,7,10,11\}$ 作为神秘顾客的编号。