Description

First, Eirin Yagokoro writes the plaintext $A$ to be encrypted. This plaintext consists of $n - 1$ positive integers.

Then, she constructs a ciphertext $B$ consisting of $n$ prime numbers, satisfying that for all $\forall i \in [1,n)$, $B_i \times B_{i + 1} = A_i$.

To improve the efficiency of information usage, Eirin Yagokoro requires that the values of all primes appearing in $B$ must be within the range $[1,M]$.

Input Format

The first line contains an integer $T$, representing the number of plaintext groups to be encrypted.

For each group of plaintext:

The first line contains two integers $n, M$, representing (plaintext length $+ 1$), i.e., the length of the ciphertext to be found, and the maximum value of primes allowed to appear.

The next line contains $n - 1$ positive integers separated by spaces, representing the plaintext $A$.

Output Format

For each group of plaintext, output one line:

• If a solution exists, output any valid ciphertext $B$. The $n$ primes in the ciphertext should be separated by spaces.

• If no solution exists, output -1.

2
4 233
55 35 77
4 5
55 35 77 

11 5 7 11 
-1

Hint

Constraints

• For $20\%$ of the testdata, $n \le 5$, $M \le 10$.

• For $40\%$ of the testdata, $A_i \le 10^{12}$.

• For $70\%$ of the testdata, $A_i \neq A_{i + 1}$.

• For $100\%$ of the testdata, $3 \le n \le 10^5$, $1 \le A_i, M \le 10^{18}$, $1 \le T \le 5$.

• The above subtasks are inclusive: $100\%$ includes $70\%$, $70\%$ includes $40\%$, $\ldots\ldots$, and so on.

Data Guarantee

• If the condition that $b_i$ must be within $[1,M]$ is ignored, there is guaranteed to be at least one valid solution.

• There exists at least one pair $(i,j)$ such that $A_i \neq A_j$.

Additional Material

This material is not very relevant to solving the problem.

Baidu Baike - Prime Number

Translated by ChatGPT 5