[SNOI2022] 倍增

小 Z 是一个喜欢编程的女孩子。 这天，她在做一道编程题的时候偶然发现了一个神奇的整数 $142857$。 $142857 \times 2 = 285714$，而 $285714$ 的所有数位恰好是 $142857$ 的一个排列。 她很好奇，有没有更大的满足这种性质的整数。 她写了一个搜索，发现了一些更大的有趣的数： $26835741 \times 2 = 53671482$ $0987312654 \times 2 = 1974625308$ $\dots$ 她不满足于解决十进制下这样的问题，于是她想知道，是否在 $B$ 进制下存在一个 $n$ 位正整数 $x$，满足 $2x$ 的所有数位在 $B$ 进制下是 $x$ 的所有数位的一个排列。 由于她讨厌数字 $0$，因此她还要求对于任意 $1 \leq i \leq n$，$x$ 和 $2x$ 在 $B$ 进制下的第 $i$ 位不能同时为 $0$。 ## Input **输入包含多组数据。** 输入的第一行是一个正整数 $T$，表示数据组数。 接下来 $T$ 行，第 $i$ 行包含两个正整数 $n$ 和 $B$，表示第 $i$ 组数据。 ## Output 对于每组数据，输出一行。 若本组数据有解，按照从高位到低位的顺序输出 $n$ 个非负整数，表示你找到的答案在 $B$ 进制下的值。 否则只需要输出一个数 $-1$。 [samples] ## Note **【样例 1 解释】** - 第一组数据的解释参见【题目描述】。 - 对于第二组数据，可以通过枚举所有的 $n$ 位 $B$ 进制数说明一定不能找到这样的正整数。 - 对于第三组数据，$2x$ 的 $7$ 进制表示为 $103635_{(7)}$，因此这是一个满足题意的答案。 注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。 **【样例 2/3 解释】** 注意此样例的答案文件仅表明了一种可能的合法答案，不表明答案文件恰好对应标准程序的输出。 **【提示】** 由于答案可能不唯一，我们下发了校验器 `checker.cpp` 和库文件 `testlib.h`。 可以使用以下命令编译 `checker.cpp`： ``` g++ -o checker checker.cpp -O2 -std=c++11 ``` 将 `checker.cpp` 编译得到可执行文件 `checker` 后你可以使用以下方式测试你的答案： `checker <input> <output> <answer>`：利用选手目录下的 `double/double*.ans` 可以用来检验你的答案在样例测试点 `double/double*.in` 的正确性。 `checker <input> <output> <output>`：会检查你的所有有解输出是否符合题目要求。注意以此种方式测试的时候，输出无解总会被报告为合法，因为在此种运行方式下我们只会检查你报告的所有解。 **请选手注意多组数据之间的清空问题。** **【数据规模与约定】** 对于全部数据，$1 \leq T \leq 10^4$，$2 \leq \sum B \leq 2 \times 10^5$，$1 \leq \sum n \leq 2 \times 10^5$，$n \geq 1$，$B \geq 2$。 具体的数据规模与约定见下表。 | 测试点编号 | $n \leq$ | $ B \leq$ | $T \leq$ | 特殊约定 | | :--------: | :-------------: | :-------------: | :------: | ------------------- | | $1$ | $8$ | $8$ | $10$ | | | $2$ | $8$ | $8$ | $10^4$ | | | $3$ | $2 \times 10^5$ | $8$ | $10$ | | | $4$ | $2 \times 10^5$ | $8$ | $10^4$ | | | $5$ | $2 \times 10^5$ | $8$ | $10^4$ | | | $6$ | $15$ | $15$ | $100$ | | | $7$ | $40$ | $40$ | $100$ | | | $8$ | $100$ | $100$ | $100$ | | | $9$ | $300$ | $300$ | $100$ | | | $10$ | $1000$ | $1000$ | $100$ | | | $11$ | $3000$ | $3000$ | $100$ | | | $12$ | $15000$ | $15000$ | $100$ | | | $13$ | $50000$ | $50000$ | $100$ | | | $14$ | $2 \times 10^5$ | $2 \times 10^5$ | $100$ | | | $15$ | $200$ | $200$ | $10^4$ | $n \geq 100$ | | $16$ | $5000$ | $5000$ | $10^4$ | $n \geq 100$ | | $17$ | $2 \times 10^5$ | $2 \times 10^5$ | $10^4$ | $n \geq 100$ | | $18$ | $300$ | $300$ | $10^4$ | $B=3k-1,k \in \N^*$ | | $19$ | $2 \times 10^5$ | $2 \times 10^5$ | $10^4$ | $B=3k-1,k \in \N^*$ | | $20$ | $300$ | $300$ | $10^4$ | $B=3k,k \in \N^*$ | | $21$ | $2 \times 10^5$ | $2 \times 10^5$ | $10^4$ | $B=3k,k \in \N^*$ | | $22$ | $100$ | $100$ | $10^4$ | | | $23$ | $500$ | $5000$ | $10^4$ | | | $24$ | $2 \times 10^5$ | $2 \times 10^5$ | $10^4$ | | | $25$ | $2 \times 10^5$ | $2 \times 10^5$ | $10^4$ | |