Problem Description

Given a sequence of length $n$, $a_1,a_2,\ldots a_n$.

You may perform several (possibly $0$) operations on this sequence. In each operation, you will:

• Choose three positive integers $i<j<k$ such that $a_i\oplus a_j\oplus a_k=0$, and the value of $k$ does not exceed the current length of the sequence. Let $s=a_i\oplus a_{i+1}\oplus \cdots\oplus a_k$.
• Then, delete $a_i$ to $a_k$, and insert $s$ at the position where these $k-i+1$ numbers originally were. Note that the length of sequence $a$ will decrease by $(k-i)$.

Determine whether it is possible to make the sequence $a$ contain only one number, that is, after all operations, the length of $a$ is $1$. If it is possible, you also need to provide one valid operation plan.

Input Format

Read input from standard input.

This problem contains multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case, the first line contains a positive integer $n$, indicating the initial length of the sequence.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, indicating the value of each element in the initial sequence.

Output Format

For each test case:

• If there exists a plan such that the sequence $a$ is reduced to only one number, output Huoyu on the first line.
  • Then, on the second line output a non-negative integer $t$, indicating the number of operations. You need to ensure $0\le t\le n$.
  • Then output $t$ lines, each containing three positive integers $i,j,k$, indicating the three numbers you choose in this operation. You need to ensure $i<j<k$ and that $k$ does not exceed the current length of the sequence.
• Otherwise, output one line containing the string Shuiniao.

2
5
3 3 1 4 5
9
3 4 6 5 4 5 1 2 4

Huoyu
2
3 4 5
1 2 3
Huoyu
3
1 3 4
2 3 4
1 2 4

Hint

[Sample Explanation #1]

For the first test case:

• In the first operation, $a_3\oplus a_4\oplus a_5=1\oplus4\oplus5=0$, and the sequence becomes $[3,3,0]$ after the operation.
• In the second operation, $a_1\oplus a_2\oplus a_3=3\oplus3\oplus0=0$, and the sequence becomes $[0]$ after the operation.

Thus, after two operations, the sequence $a$ contains only one number.

For the second test case:

• In the first operation, $a_1\oplus a_3\oplus a_4=3\oplus6\oplus5=0$, $s=4$, and the sequence becomes $[4,4,5,1,2,4]$ after the operation.
• In the second operation, $a_2\oplus a_3\oplus a_4=4\oplus5\oplus1=0$, and the sequence becomes $[4,0,2,4]$ after the operation.
• In the third operation, $a_1\oplus a_2\oplus a_4=4\oplus0\oplus4=0$, $s=2$, and the sequence becomes $[2]$ after the operation.

Thus, after three operations, the sequence $a$ contains only one number.

[Sample #2]

See merge/merge2.in and merge/merge2.ans under the contestant directory.

This sample satisfies the constraints of test points $6\sim7$.

[Sample #3]

See merge/merge3.in and merge/merge3.ans under the contestant directory.

This sample satisfies the constraints of test points $12\sim13$.

[Constraints]

For all testdata, it is guaranteed that: $1\leq T\leq20$, $1\leq n\leq500$, $0\leq a_i<512$.

[Note]

$\oplus$ denotes the bitwise XOR operation.

Please fully trust the constant factors and efficiency of the program.

Translated by ChatGPT 5