Background

After the Moon War, Yukari Yakumo set up a barrier in the Huai'an Passage, causing all information sent from the surface to the Lunar Capital to be intercepted and decrypted.

To maintain normal communication, Eirin Yagokoro and the moon rabbits developed a brand-new encryption method.

Problem 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