Corte#13088
Se te da un arreglo formado por números enteros. Definimos un corte como la partición del arreglo en tres subarreglos contiguos no vacíos tales que los residuos módulo de sus sumas sean distintos dos a dos.
Formalmente, elige dos enteros (1 \le x < y \le n) tales que el arreglo quede dividido en los siguientes tres bloques contiguos: [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].
Sean 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.
La partición se considera un corte válido si S_1,S_2,S_3 son distintos dos a dos; es decir: S_1 \ne S_2 , S_1 \ne S_3 , S_2 \ne S_3.
Encuentra cualquier corte válido del arreglo o determina que no existe ningún corte válido.
Aquí c \bmod d denota el operador módulo, el residuo que queda al dividir entre ; por ejemplo, 19 \bmod 4 = 3 porque al dividir entre queda un residuo de .
La primera línea contiene un único entero (1 \le t \le 10^4) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene un único entero (3 \le n \le 10^5) — la longitud del arreglo .
La segunda línea contiene enteros separados a_1,a_2,...,a_n (1 \le a_1,a_2,...,a_n \le 10^9) — el arreglo
Se garantiza que la suma de sobre todos los casos de prueba no excede 10^5.
Para cada caso de prueba, si existe un corte válido, imprime dos enteros e que lo describen. En caso contrario, imprime .
Ejemplo 1
En el primer caso de prueba, se puede demostrar que no existe ningún corte válido.
En el segundo caso de prueba, el arreglo se divide en tres segmentos:
[a_1,a_2,a_3,a_4]=[6,3,9,4], para el cual \sum([6,3,9,4])=22, y 22 \bmod 3=1
[a_5,a_6,a_7,a_8]=[5,7,12,2], para el cual \sum([5,7,12,2])=26, y 26 \bmod 3=2
[a_9,a_{10}]=[8,1], para el cual \sum([8,1])=9, y 9 \bmod 3=0
Por lo tanto, x=4, y=8 describe un corte válido.
En el tercer caso de prueba, el arreglo se divide en tres segmentos:
[a_1,a_2,a_3,a_4,a_5,a_6]=[10,4,2,3,5,11], para el cual \sum([10,4,2,3,5,11])=35, y 35 \bmod 3=2
[a_7]=[1], para el cual \sum([1])=1, y 1 \bmod 3=1
[a_8,a_9,a_{10},a_{11}]=[3,6,9,15], para el cual \sum([3,6,9,15])=33, y 33 \bmod 3=0
Por lo tanto, x=6, y=7 describe un corte válido.
Subtarea ( puntos): (1 \le \sum n \le 100)
Subtarea ( puntos): (1 \le \sum n \le 1000)
Subtarea ( puntos): Sin restricciones adicionales