Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Трое в лодке, не считая торт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса, Боб и Чарли хотят разделить прямоугольный торт, разрезанный на $$$n$$$ частей. Каждый считает, что каждый кусок торта имеет определённую ценность. Алиса считает, что $$$i$$$-й кусок имеет ценность $$$a_i$$$, Боб — $$$b_i$$$, а Чарли — $$$c_i$$$.

Суммы всех $$$a_i$$$, всех $$$b_i$$$ и всех $$$c_i$$$ по отдельности одинаковы и равны $$$tot$$$.

Учитывая ценности каждого куска торта для каждого человека, нужно дать каждому человеку несколько подряд идущих кусков торта. Другими словами, индексы левых и правых концов этих подотрезков (номера кусков, отданных определённому человеку) можно представить как $$$(l_a, r_a)$$$, $$$(l_b, r_b)$$$ и $$$(l_c, r_c)$$$ для Алисы, Боба и Чарли соответственно. Разбиение должно удовлетворять следующим условиям:

  • Ни один кусок не отдан более чем одному человеку, т.е. никакие два подотрезка из $$$[l_a,\ldots,r_a]$$$, $$$[l_b, \ldots, r_b]$$$ и $$$[l_c, \ldots, r_c]$$$ не пересекаются.
  • Каждая из трёх сумм $$$ \sum_{i = l_a}^{r_a} a_i, \sum_{i = l_b}^{r_b} b_i, \sum_{i = l_c}^{r_c} c_i \geq \lceil \frac{tot}{3} \rceil$$$.

Здесь запись $$$\lceil \frac{a}{b} \rceil$$$ обозначает деление с округлением вверх. Результат равен наименьшему целому числу, большему или равному результату точного деления $$$a$$$ на $$$b$$$. Иными словами, результат деления округляется вверх до ближайшего целого. Например, $$$\lceil \frac{10}{3} \rceil = 4$$$ и $$$\lceil \frac{15}{3} \rceil = 5$$$.

Входные данные

Первая строка содержит целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 10^4$$$)

Для каждого набора входных данных:

Первая строка содержит целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).

Следующие три строки содержат по $$$n$$$ целых чисел:

Одна строка с $$$n$$$ целыми числами $$$a_1, a_2, \ldots, a_n$$$ представляет ценности для Алисы ($$$1 \le a_i \le 10^6$$$).

Следующая строка с $$$n$$$ целыми числами $$$b_1, b_2, \ldots, b_n$$$ представляет ценности для Боба ($$$1 \le b_i \le 10^6$$$).

Следующая строка с $$$n$$$ целыми числами $$$c_1, c_2, \ldots, c_n$$$ представляет ценности для Чарли ($$$1 \le c_i \le 10^6$$$).

Гарантируется, что $$$ \sum_{i = 1}^{n} a_i = \sum_{i = 1}^{n} b_i = \sum_{i = 1}^{n} c_i$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$-1$$$, если искомые подотрезки не существуют.

В противном случае выведите шесть чисел: $$$l_a, r_a, l_b, r_b, l_c, r_c$$$ — соответствующие начальные и конечные индексы (в $$$1$$$-индексации) подотрезков для Алисы, Боба и Чарли соответственно.

Пример
Входные данные
10
5
5 1 1 1 1
1 1 5 1 1
1 1 1 1 5
6
1 2 3 4 5 6
5 6 1 2 3 4
3 4 5 6 1 2
4
4 4 4 4
4 4 4 4
4 4 4 4
5
5 10 5 2 10
9 6 9 7 1
10 7 10 2 3
3
4 5 2
6 1 4
1 8 2
3
10 4 10
8 7 9
10 4 10
7
57113 65383 19795 53580 74452 3879 23255
12917 16782 89147 93107 27365 15044 43095
33518 63581 33565 34112 46774 44151 41756
6
6 3 1 8 7 1
10 2 6 2 2 4
10 9 2 1 2 2
5
5 5 4 5 5
1 6 3 8 6
2 4 1 9 8
10
1 1 1 1 1001 1 1 1001 1 1
1 1 1 1 1 1 2001 1 1 1
1 1 1 1 1 1001 1 1 1 1001
Выходные данные
1 1 2 3 4 5 
5 6 1 2 3 4 
-1
-1
1 1 3 3 2 2 
-1
1 2 3 4 5 7 
3 6 1 1 2 2 
1 2 3 4 5 5 
1 5 6 7 8 10
Примечание

В первом наборе входных данных сумма каждого из трех массивов равна $$$9$$$. Каждому человеку нужна часть торта, соответствующая подотрезку с суммарной ценностью не менее $$$\lceil \frac{9}{3} \rceil = 3$$$.

Если мы назначим подотрезок ($$$1$$$,$$$1$$$) Алисе, то его общая ценность для нее составит $$$5$$$, что $$$\ge 3$$$; назначим подотрезок ($$$2$$$,$$$3$$$) Бобу, общая ценность для него составит $$$1 + 5 = 6$$$, что $$$\ge 3$$$; и назначим подотрезок ($$$4$$$,$$$5$$$) Чарли, общая ценность для него составит $$$1 + 5 = 6$$$, что также $$$\ge 3$$$. Каждый человек получает свои куски торта, и ни один кусок не является общим для двух или более человек.

Можно показать, что для третьего набора входных данных невозможно раздать кусочки торта таким образом, чтобы удовлетворить заданным условиям.