#P1699. 2024.03.16-MY-第三题-数组变换

2024.03.16-MY-第三题-数组变换

题目描述

塔子哥有一个长度为 n 的数组 a。他想要使得所有aia_i的最大公因子是一个素数。即:gcd(a1,a2,...,an)gcd(a_1,a_2,...,a_n)是一个素数。他可以对数组进行任意次操作。具体的:每次操作,他会选择i,ji,j两个下标,同时执行:ai=ai+2,aj=aj2a_i=a_i+2,a_j=a_j-2

请问他是否有可能在任意次操作内将数组变成符合要求的,如果可以,请输出所有可能的最大公因数。注意,这里要保证aja_j,在操作后仍然是正数,即不能选择aj2a_j\le 2.

输入描述

输入两行,第一行一个正整数n(2n21e5)n(2\le n \le 2*1e5)表示数组长度。

第二行nn个整数ai([1,1e6])a_i([1,1e6])

输出描述

输入包含一行或两行。如果可以输出“YES”否则输出“NO”(不含双引号)

如果答案为“YES”,则第二行按照升序输出所有可行的数组 gcd.

样例

输入

4
1 3 5 9

输出

YES
3

说明

可以选择一次i=1,j=3,这样一来数组变成:[3,3,3,9], gcd =3.可以证明只有 3这一个答案。

输入

4
2 2 2 2

输出

YES
2