P6523 "Wdoi-1" Encrypted Communication

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.

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]$.

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$.

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`.

#### 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](https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0/263515?fr=aladdin) Translated by ChatGPT 5