Розрізання#13088
Дано масив , що складається з цілих чисел. Визначимо розрізання як поділ масиву на три непорожні неперервні підмасиви так, щоб остачі від ділення на сум цих підмасивів були попарно різними.
Формально, виберіть два цілі числа (1 \le x < y \le n) так, щоб масив було розбито на такі три неперервні блоки: [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].
Нехай 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.
Розбиття вважається коректним розрізанням, якщо S_1,S_2,S_3 попарно різні; тобто: S_1 \ne S_2 , S_1 \ne S_3 , S_2 \ne S_3.
Знайдіть будь-яке коректне розрізання масиву або визначте, що коректних розрізань не існує.
Тут c \bmod d позначає оператор остачі; це остача, що залишається після ділення на . Наприклад, 19 \bmod 4 = 3, оскільки при діленні на залишається .
Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість наборів входних даних.
Перший рядок кожного набору входних даних містить одне ціле число (3 \le n \le 10^5) — довжину масиву .
Другий рядок містить розділених пробілами цілих чисел a_1,a_2,...,a_n (1 \le a_1,a_2,...,a_n \le 10^9) — масив
Гарантується, що сума по всіх наборах входних даних не перевищує 10^5.
Для кожного набору входних даних, якщо існує коректне розрізання, виведіть два цілі числа і , які його описують. Інакше виведіть .
Приклад 1
У першому наборі входних даних можна показати, що коректного розрізання не існує.
У другому наборі входних даних масив розбито на три сегменти:
[a_1,a_2,a_3,a_4]=[6,3,9,4], для якого \sum([6,3,9,4])=22, а отже 22 \bmod 3=1
[a_5,a_6,a_7,a_8]=[5,7,12,2], для якого \sum([5,7,12,2])=26, а отже 26 \bmod 3=2
[a_9,a_{10}]=[8,1], для якого \sum([8,1])=9, а отже 9 \bmod 3=0
Отже, x=4, y=8 описує коректне розрізання.
У третьому наборі входних даних масив розбито на три сегменти:
[a_1,a_2,a_3,a_4,a_5,a_6]=[10,4,2,3,5,11], для якого \sum([10,4,2,3,5,11])=35, а отже 35 \bmod 3=2
[a_7]=[1], для якого \sum([1])=1, а отже 1 \bmod 3=1
[a_8,a_9,a_{10},a_{11}]=[3,6,9,15], для якого \sum([3,6,9,15])=33, а отже 33 \bmod 3=0
Отже, x=6, y=7 описує коректне розрізання.
Підзадача ( балів): (1 \le \sum n \le 100)
Підзадача ( балів): (1 \le \sum n \le 1000)
Підзадача ( балів): Без додаткових обмежень