Problem Description

You are given an integer sequence $a$ of length $n$, where each value is in $[0,2]$. One operation is defined as follows:

• Choose an index $x$ ($1 \le x \le n - 2$).
• Let $s=(a_x+a_{x+1}+a_{x+2}) \bmod 3$, then change $a_x, a_{x+1}, a_{x+2}$ all to $s$ at the same time.

You need to perform several operations (possibly none) to maximize the sum of all numbers in the sequence $a$. At the same time, you must provide a valid operation plan whose number of operations does not exceed $\left\lfloor\dfrac{5}{7}n\right\rfloor+100$. It can be proven that a plan satisfying the operation limit always exists.

Input Format

The first line contains an integer $T$ ($1 \le T \le 1000$), the number of test cases. Then follow $T$ blocks, each describing one test case:

• The first line contains an integer $n$ ($3 \le n \le 10^6$), the length of the sequence $a$.
• The second line contains $n$ integers; the $i$-th integer is $a_i$ ($0 \le a_i \le 2$).

The data guarantees that $\sum n \le 10^6$.

Output Format

For each test case:

• The first line outputs two integers $s$ and $K$, representing the maximum possible sequence sum and the number of operations in your plan. You must ensure $0 \le K \le \left\lfloor\dfrac{5}{7}n\right\rfloor + 100$.
• The next line outputs $K$ positive integers; the $i$-th integer is the chosen $x$ for the $i$-th operation.

3
3
0 1 0
5
0 2 1 2 2
7
1 1 1 1 1 1 1

3 1
1
10 4
2 2 3 1
14 5
1 3 4 5 1

Hint

Translated by ChatGPT 5