Powerful Ksenia

1000ms

262144K

Description:

Ksenia has an array $$$a$$$ consisting of $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$.

In one operation she can do the following:

choose three distinct indices $$$i$$$, $$$j$$$, $$$k$$$, and then
change all of $$$a_i, a_j, a_k$$$ to $$$a_i \oplus a_j \oplus a_k$$$ simultaneously, where $$$\oplus$$$ denotes the bitwise XOR operation.

She wants to make all $$$a_i$$$ equal in at most $$$n$$$ operations, or to determine that it is impossible to do so. She wouldn't ask for your help, but please, help her!

Input:

The first line contains one integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the length of $$$a$$$.

The second line contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of $$$a$$$.

Output:

Print YES or NO in the first line depending on whether it is possible to make all elements equal in at most $$$n$$$ operations.

If it is possible, print an integer $$$m$$$ ($$$0 \leq m \leq n$$$), which denotes the number of operations you do.

In each of the next $$$m$$$ lines, print three distinct integers $$$i, j, k$$$, representing one operation.

If there are many such operation sequences possible, print any. Note that you do not have to minimize the number of operations.

Sample Input:

5
4 2 1 7 2

Sample Output:

YES
1
1 3 4

Sample Input:

4
10 4 49 22

Sample Output:

NO

Note:

In the first example, the array becomes $$$[4 \oplus 1 \oplus 7, 2, 4 \oplus 1 \oplus 7, 4 \oplus 1 \oplus 7, 2] = [2, 2, 2, 2, 2]$$$.

Informação

Provedor Codeforces

Código CF1438D