题目背景

自月战之后，八云紫在槐安通道中设立了一重结界，使得从地面传向月都的信息全部会被拦截和破译。

为了维持正常的通讯，八意永琳同月兔们研究出了一种全新的加密方式。

题目描述

首先，八意永琳会写出需要被加密的明文 $A$ ，此段明文由 $n-1$ 个正整数构成。

之后，她会构造出一个由 $n$ 个质数构成的密文 $B$，满足对 $\forall i \in [1,n),B_i \times B_{i + 1} = A_i$。

为了提高信息的利用率，八意永琳规定 $B$ 中出现的所有质数的值必须在 $[1,M]$ 范围内。

输入格式

第一行一个整数 $T$ , 表示需要被加密的明文的组数。

对于每组明文：

第一行两个整数 $n,M$ ，代表明文的长度$+1$，也即所求密文的长度和可出现质数的最大值。

接下来一行 $n - 1$ 个由空格隔开的正整数，代表明文 $A$。

输出格式

对于每组明文，均输出一行：

• 若有解，输出任意一组合法密文 $B$ 即可，密文中的 $n$ 个质数以空格隔开。

• 若无解，输出 -1。

2
4 233
55 35 77
4 5
55 35 77 

11 5 7 11 
-1

提示

数据规模

• 对于 $20\%$ 的数据，$n \le 5,M \le 10$。

• 对于 $40\%$ 的数据，$A_i \le 10 ^ {12}$。

• 对于 $70\%$ 的数据， $A_i \neq A_{i + 1}$。

• 对于$100\%$的数据，$3 \le n \le 10 ^ 5$，$1 \le A_i,M \le 10 ^ {18}$，$1 \le T \le 5$。

• 以上几档部分分呈包含关系，$100\%$ 包含 $70\%$，$70\%$ 包含 $40\%\ \ldots\ldots$以此类推。

数据保证：

• 若不考虑 $b_i$ 在 $[1,M]$ 范围内的条件，必然有至少一组合法解。

• 有至少一对 $(i,j)$，使得 $A_i \neq A_j$。

后置资料

本段资料与答题相关性不大。

百度百科 - 质数