Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Powerful Ksenia

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputKsenia 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.

Examples

Input

5 4 2 1 7 2

Output

YES 1 1 3 4

Input

4 10 4 49 22

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]$$$.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/06/2022 20:12:53 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|