← 返回题目列表

Codeforces · 1081/E

E. 缺失号码

中文机器翻译题面 查看原题

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$$$ 是另一个答案。

在第三个示例中,可以表明不存在这样的序列。