#3729. 「SNOI2022」倍增

题目描述

小 Z 是一个喜欢编程的女孩子。

这天，她在做一道编程题的时候偶然发现了一个神奇的整数 $142857$。

$142857 \times 2 = 285714$，而 $285714$ 的所有数位恰好是 $142857$ 的一个排列。

她很好奇，有没有更大的满足这种性质的整数。

她写了一个搜索，发现了一些更大的有趣的数：

$26835741 \times 2 = 53671482$

$0987312654 \times 2 = 1974625308$

$\dots$

她不满足于解决十进制下这样的问题，于是她想知道，是否在 $B$ 进制下存在一个 $n$ 位正整数 $x$，满足 $2x$ 的所有数位在 $B$ 进制下是 $n$ 的所有数位的一个排列。

由于她讨厌数字 $0$，因此她还要求对于任意 $1 \leq i \leq n$，$x$ 和 $2x$ 在 $B$ 进制下的第 $i$ 位不能同时为 $0$。

输入格式

输入包含多组数据。

输入的第一行是一个正整数 $T$，表示数据组数。

接下来 $T$ 行，第 $i$ 行包含两个正整数 $n$ 和 $B$，表示第 $i$ 组数据。

输出格式

对于每组数据，输出一行。

若本组数据有解，按照从高位到低位的顺序输出 $n$ 个非负整数，表示你找到的答案在 $B$ 进制下的值。

否则只需要输出一个数 $-1$。

---

样例 1

输入

3
6 10
3 3
6 7

输出

1 4 2 8 5 7
-1
0 3 5 3 1 6

第一组数据的解释参见「题目描述」。

对于第二组数据，可以通过枚举所有的 $n$ 位 $B$ 进制数说明一定不能找到这样的正整数。

对于第三组数据，$2x$ 的 $7$ 进制表示为 $103635_{(7)}$，因此这是一个满足题意的答案。

注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。

---

样例 2

见附加文件中 double2.in 和 double2.ans。

本组数据满足测试点 $3$ 的限制。

注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。

---

样例 3

见附加文件中 double3.in 和 double3.ans。

本组数据满足测试点 $17$ 的限制。

注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。

---

提示

由于答案可能不唯一，我们下发了校验器 check.cpp 和库文件 testlib.h。

可以使用以下命令编译 checker.cpp：

g++ -o checker checker.cpp -O2 -std=c++11

将 check.cpp 编译得到可执行文件 checker 后你可以使用以下方式测试你的答案：

• checker <input> <output> <answer>：利用选手目录下的 double*.ans 可以用来检验你的答案在样例测试点 double*.in 的正确性。

• checker <input> <output> <output>：会检查你对这组数据的所有有解输出是否符合题目要求。注意以此种方式测试的时候，输出无解总会被报告为合法。

请选手注意多组数据之间的清空问题。

---

数据范围与约定

对于全部数据，$1 \le T \le 10^4$，$2 \le \sum B \le 2 \times 10^5$，$1 \le \sum n \le 2 \times 10^5$，$n \ge 1$，$B \ge 2$。

具体的数据规模与约定见下表。

测试点编号	$n$	$B$	$T$	特殊约定
1	$\le 8$		$\le 10$	无
2	$\le 10^4$
3	$\le 2\times 10^5$	$\le 10$
4	$\le 10^4$
5
6	$\le 15$		$\le 100$	无
7	$\le 40$
8	$\le 100$
9	$\le 300$
10	$\le 1000$
11	$\le 3000$
12	$\le 15000$
13	$\le 50000$
14	$\le 2\times 10^5$
15	$\le 200$		$\le 10^4$	$n\ge 100$
16	$\le 5000$
17	$\le 2\times 10^5$
18	$\le 300$			$B = 3k - 1$，$k$ 为正整数
19	$\le 2\times 10^5$
20	$\le 300$			$B = 3k$，$k$ 为正整数
21	$\le 2\times 10^5$
22	$\le 100$			无
23	$\le 5000$
24	$\le 2\times 10^5$
25

---