加密通信

题目描述

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

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

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

输入格式

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

对于每组明文：

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

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

输出格式

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

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

输入输出样例

输入 #1

1
2
3
4
5
2
4 233
55 35 77
4 5
55 35 77

输出 #1

1
2
11 5 7 11 
-1

数据保证：

  • 若不考虑 b_i 在 [1,M] 范围内的条件，必然有至少一组合法解。
  • 有至少一对 (i,j)，使得 $a_i \ne a_{i+1}$ 。

题解

题目数据保证，至少有一对 $a_i \ne a_{i+1}$。

因为 $a_i$ 都是两个质数相乘的形式， $a_i \ne a_{i+1}$，所以 $a_i$ 和 $a_{i+1}$ 至多只有一个公因子，所以 $b_i=gcd(a_i,a_{i+1})$ 。

从不相等的这处开始向两边扩展。