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