Slicing#13088
You are given an array consisting of integers. We define a slicing as partitioning the array into three non-empty contiguous subarrays such that the remainders modulo of their sums are pairwise distinct.
Formally, choose two integers (1 \le x < y \le n) such that the array is partitioned into the following three contiguous blocks: [a_1,a_2,\dots,a_x], [a_{x+1},a_{x+2},\dots,a_y], [a_{y+1},a_{y+2},\dots,a_n].
Let S_1=\left(\sum\limits_{i=1}^{x} a_i\right)\bmod 3 , S_2=\left(\sum\limits_{i=x+1}^{y} a_i\right)\bmod 3 , S_3=\left(\sum\limits_{i=y+1}^{n} a_i\right)\bmod 3.
The partition is considered a valid slicing if S_1,S_2,S_3 are pairwise distinct; that is: S_1 \ne S_2 , S_1 \ne S_3 , S_2 \ne S_3.
Find any valid slicing of the array or determine that it does not have valid slicings.
Here c \bmod d denotes The Modulo Operator, the remainder left when is divided by ; for example, 19 \bmod 4 = 3 because divided by leaves left over.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
The first line of each test case contains a single integer (3 \le n \le 10^5) — the length of the array .
The second line contains separated integers a_1,a_2,...,a_n (1 \le a_1,a_2,...,a_n \le 10^9) — the array
It's guaranteed that the sum of overall test cases doesn't exceed 10^5.
For each test case , if there exists a valid slicing , output two integers and which describe it. Otherwise, output .
Example 1
In the first test case , it can be shown that there's no valid slicing.
In the second test case , the array is partitioned into three segments :
[a_1,a_2,a_3,a_4]=[6,3,9,4] which has \sum([6,3,9,4])=22 which is 22 \bmod 3=1
[a_5,a_6,a_7,a_8]=[5,7,12,2] which has \sum([5,7,12,2])=26 which is 26 \bmod 3=2
[a_9,a_{10}]=[8,1] which has \sum([8,1])=9 which is 9 \bmod 3=0
Thus x=4, y=8 describes a valid slicing.
In the third test case , the array is partitioned into three segments :
[a_1,a_2,a_3,a_4,a_5,a_6]=[10,4,2,3,5,11] which has \sum([10,4,2,3,5,11])=35 which is 35 \bmod 3=2
[a_7]=[1] which has \sum([1])=1 which is 1 \bmod 3=1
[a_8,a_9,a_{10},a_{11}]=[3,6,9,15] which has \sum([3,6,9,15])=33 which is 33 \bmod 3=0
Thus x=6, y=7 describes a valid slicing.
Subtask ( points): (1 \le \sum n \le 100)
Subtask ( points): (1 \le \sum n \le 1000)
Subtask ( points): No additional constraints