给你一个 $$$n$$$ 整数数组。您需要将所有整数分成两组,以便第一组中所有整数的 GCD 等于 1,第二组中所有整数的 GCD 等于 1。
一组整数的 GCD 是整除该组中所有整数的最大非负整数。
两个组都必须非空。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组的元素。
输出
如果可以根据需要将整数分成两组,则在第一行打印“YES”(不带引号),否则打印“NO”(不带引号)。
如果可以拆分整数,则在第二行中打印 $$$n$$$ 个整数,其中如果整数 $$$a_i$$$ 应位于第一组中,则第 $$$i$$$ 个整数等于 $$$1$$$,否则为 $$$2$$$。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
4 2 3 6 7
输出 #1
YES 2 2 1 1
输入 #2
5 6 15 35 77 22
输出 #2
YES 2 1 2 1 1
输入 #3
5 6 10 15 1000 75
输出 #3
NO