Олимпиадный тренинг

Задача . C. Трое в лодке, не считая торт


Алиса, Боб и Чарли хотят разделить прямоугольный торт, разрезанный на \(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\)-индексации) подотрезков для Алисы, Боба и Чарли соответственно.

Примечание

В первом наборе входных данных сумма каждого из трех массивов равна \(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\). Каждый человек получает свои куски торта, и ни один кусок не является общим для двух или более человек.

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


Примеры
№Входные данныеВыходные данные
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
Статистика успешных решений по компиляторам
 Кол-во
С++3