P8361 [SNOI2022] Doubling

Xiao Z is a girl who likes programming. One day, while solving a programming problem, she accidentally found a magical integer $142857$. $142857 \times 2 = 285714$, and all digits of $285714$ are exactly a permutation of the digits of $142857$. She was curious whether there exists a larger integer with this property. She wrote a search program and found some larger interesting numbers: $26835741 \times 2 = 53671482$ $0987312654 \times 2 = 1974625308$ $\dots$ She is not satisfied with only the decimal case. So she wants to know whether, in base $B$, there exists an $n$-digit positive integer $x$ such that all digits of $2x$ in base $B$ are a permutation of all digits of $x$ in base $B$. Since she hates the digit $0$, she also requires that for any $1 \leq i \leq n$, the $i$-th digit of $x$ and the $i$-th digit of $2x$ in base $B$ cannot both be $0$ at the same time.

**The input contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. The next $T$ lines each contain two positive integers $n$ and $B$, describing one test case.

For each test case, output one line. If there is a solution for this test case, output $n$ non-negative integers from the most significant digit to the least significant digit, representing the value of your answer in base $B$. Otherwise, output a single number $-1$.

**[Sample 1 Explanation]** - The explanation of the first test case can be found in the **Description**. - For the second test case, you can prove that such a positive integer cannot be found by enumerating all $n$-digit base-$B$ numbers. - For the third test case, the base-$7$ representation of $2x$ is $103635_{(7)}$, so this is a valid answer. Note that the sample output only shows one possible valid answer, and it does not mean the sample output must exactly match the output of the standard solution. **[Sample 2/3 Explanation]** Note that the sample output only shows one possible valid answer, and it does not mean the sample output must exactly match the output of the standard solution. **[Hint]** Since the answer may not be unique, we provide a checker `checker.cpp` and a library file `testlib.h`. You can compile `checker.cpp` using the following command: ``` g++ -o checker checker.cpp -O2 -std=c++11 ``` After compiling `checker.cpp` into an executable file `checker`, you can test your output as follows: `checker `: the files `double/double*.ans` under the contestant directory can be used to verify the correctness of your output on the sample test points `double/double*.in`. `checker `: it will check whether all outputs you claim to have solutions satisfy the problem requirements. Note that in this testing mode, reporting no solution will always be judged as valid, because in this mode we only check all solutions you output. **Please pay attention to clearing data structures between multiple test cases.** **[Constraints and Conventions]** For all testdata, $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$. The detailed constraints are shown in the table below. | Test Point ID | $n \leq$ | $ B \leq$ | $T \leq$ | Special Constraints | | :-----------: | :-------------: | :-------------: | :------: | ------------------------------ | | $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$ | | Translated by ChatGPT 5