← 返回题目列表

Codeforces · 1438/D

D. 强大的克塞尼亚

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

Ksenia 有一个数组 $$$a$$$,由 $$$n$$$ 正整数 $$$a_1、a_2、\ldots、a_n$$$ 组成。

在一次操作中,她可以执行以下操作:

- 选择三个不同的索引 $$$i$$$、$$$j$$$、$$$k$$$,然后
- 同时将 $$$a_i、a_j、a_k$$$ 全部更改为 $$$a_i \oplus a_j \oplus a_k$$$,其中 $$$\oplus$$$ 表示按位异或运算。

她希望在最多 $$$n$$$ 操作中使所有 $$$a_i$$$ 相等,或者确定不可能这样做。她不会请求你的帮助,但请帮助她!

输入

第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — $$$a$$$ 的元素。

输出

在第一行打印 YES 或 NO,具体取决于是否可以在最多 $$$n$$$ 操作中使所有元素相等。

如果可能,打印一个整数 $$$m$$$ ($$$0 \leq m \leq n$$$),它表示您执行的操作数。

在接下来的 $$$m$$$ 行中,打印三个不同的整数 $$$i, j, k$$$,代表一个操作。

如果有许多这样的操作序列可能,则打印任何一个。请注意,您不必最小化操作数量。

示例

输入 #1

5
4 2 1 7 2

输出 #1

YES
1
1 3 4

输入 #2

4
10 4 49 22

输出 #2

NO

注意

在第一个示例中,数组变为 $$$[4 \oplus 1 \oplus 7, 2, 4 \oplus 1 \oplus 7, 4 \oplus 1 \oplus 7, 2] = [2, 2, 2, 2, 2]$$$。