Couti 正在研究一个奇怪的数学问题。
有一个 $$$n$$$ 正整数 $$$x_1, x_2, \ldots, x_n$$$ 序列,其中 $$$n$$$ 是偶数。该序列非常特殊,即对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$t$$$,$$$x_1+x_2+...+x_t$$$ 是某个整数的平方(即完美平方)。
不知何故,奇数索引的数字消失了,所以他只知道偶数位置上的数字,即 $$$x_2, x_4, x_6, \ldots, x_n$$$。他的任务就是恢复原来的顺序。再次,轮到你帮助他了。
问题设置者可能会犯错误,因此根本不存在可能的序列。如果有多个可能的序列,则可以输出任何一个。
输入
第一行包含偶数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。
第二行包含 $$$\frac{n}{2}$$$ 正整数 $$$x_2, x_4, \ldots, x_n$$$ ($$$1 \le x_i \le 2 \cdot 10^5$$$)。
输出
如果没有可能的序列,则打印“No”。
否则,打印“Yes”,然后打印 $$$n$$$ 正整数 $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^{13}$$$),其中 $$$x_2, x_4, \ldots, x_n$$$ 应与输入数据中的相同。如果有多个答案,请打印其中一个。
请注意,$$$x_i$$$ 的限制大于输入数据的限制。可以证明,如果有答案,则必然存在满足$$$1 \le x_i \le 10^{13}$$$的可能序列。
示例
输入 #1
6 5 11 44
输出 #1
Yes 4 5 16 11 64 44
输入 #2
2 9900
输出 #2
Yes 100 9900
输入 #3
6 314 1592 6535
输出 #3
No
注意
在第一个示例中
- $$$x_1=4$$$
- $$$x_1+x_2=9$$$
- $$$x_1+x_2+x_3=25$$$
- $$$x_1+x_2+x_3+x_4=36$$$
- $$$x_1+x_2+x_3+x_4+x_5=100$$$
- $$$x_1+x_2+x_3+x_4+x_5+x_6=144$$$
在第二个示例中,$$$x_1=100$$$,$$$x_1+x_2=10000$$$。它们都是完美的正方形。还有其他可能的答案。例如,$$$x_1=22500$$$ 是另一个答案。
在第三个示例中,可以表明不存在这样的序列。