题目背景
在数字王国中,国王需要为宝库设置一系列密码。然而王国的古老魔法有一个禁忌:任何一段连续密码的数字之和,都绝对不能是神秘数字 $k$ 的倍数,否则警报就会响起。
题目描述
你需要构造一个严格递增的正整数序列 $a_1 < a_2 < \dots < a_n$,使得对任意 $1 \le l \le r \le n$,都有
$$k \nmid \sum_{i=l}^{r} a_i$$
即任意一个长度至少为 $1$ 的连续子段之和都不是 $k$ 的倍数。
在所有满足条件的序列中,求出字典序最小的一个(字典序比较:自左向右逐位比较,先出现较小元素者更小)。若不存在任何满足条件的序列,输出 $-1$。
本题有多组测试数据。
输入格式
第一行一个整数 $T$,表示测试数据组数。
接下来 $T$ 行,每行两个整数 $n, k$,表示一组询问。
输出格式
对于每组测试数据:
- 若存在满足条件的序列,输出一行 $n$ 个空格分隔的整数,表示字典序最小的序列;
- 否则输出一行 $-1$。
注:由于未知原因,请不要输出行末空格。
样例
样例 1 输入
3
3 3
2 3
4 5
样例 1 输出
-1
1 4
1 2 4 7
样例 1 说明
第二组:序列 $[1, 4]$ 的连续段和为 $1, 4, 5$,均不是 $3$ 的倍数,且为字典序最小。
数据范围与提示
| 测试点编号 | 特殊性质 | 分值 |
|---|---|---|
| $1 \sim 2$ | $n, k \le 8$ 且 $T \le 10$ | $20$ |
| $3 \sim 4$ | 所有数据满足 $n \ge k$ | $20$ |
| $5 \sim 7$ | $T \le 20$ 且 $k \le 2000$ | $30$ |
| $8 \sim 10$ | 无特殊限制 | $30$ |
对于全部数据:$1 \le T \le 10^5$,$1 \le n, k \le 2 \times 10^5$,且所有测试数据的 $k$ 之和不超过 $5 \times 10^5$。
时间限制:1 秒;内存限制:512 MB。
