Description

Congcong and Ruirui have become obsessed with a game called Split.

The rules are as follows: There are $n$ bottles labeled $0, 1, \ldots, n-1$. Bottle $i$ initially contains $p_i$ chocolate beans. The two players take turns. On each turn, a player chooses three bottles with indices $i, j, k$ such that $i \lt j$ and $j \leq k$, and bottle $i$ must contain at least $1$ bean. The player removes one bean from bottle $i$ and adds one bean to each of bottles $j$ and $k$ (note that $j$ may equal $k$). If it is a player’s turn and they cannot make a move following the rules, they lose. The winner takes all the chocolate beans.

Congcong moves first. He wants to know whether he can force a win given the initial numbers of beans in each bottle. He also wants you to tell him how to play the first move, and, to ensure victory, how many different first moves there are.

Input Format

The first line of input contains an integer $t$, the number of test cases.

For each test case, the first line contains the number of bottles $n$. The next line contains $n$ space-separated non-negative integers, the number of beans in each bottle.

Output Format

For each test case, output two lines. The first line contains three integers separated by single spaces, representing the indices $i, j, k$ that should be chosen on the first move to guarantee a win. If there are multiple valid answers, output the lexicographically smallest triple. If it is impossible to win no matter what, output three $-1$ separated by single spaces.

The second line contains the number of distinct first moves that ensure a win.

2
4
1 0 1 5000
3
0 0 1

0 2 3
1
-1 -1 -1
0

Hint

Constraints: $1 \leq t \leq 10$, $2 \leq n \leq 21$, $0 \leq p_i \leq 10^4$.

Translated by ChatGPT 5