Алиса, Боб и Чарли хотят разделить прямоугольный торт, разрезанный на $$$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)$$$ для Алисы, Боба и Чарли соответственно. Разбиение должно удовлетворять следующим условиям:
Здесь запись $$$\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$$$-индексации) подотрезков для Алисы, Боба и Чарли соответственно.
1055 1 1 1 11 1 5 1 11 1 1 1 561 2 3 4 5 65 6 1 2 3 43 4 5 6 1 244 4 4 44 4 4 44 4 4 455 10 5 2 109 6 9 7 110 7 10 2 334 5 26 1 41 8 2310 4 108 7 910 4 10757113 65383 19795 53580 74452 3879 2325512917 16782 89147 93107 27365 15044 4309533518 63581 33565 34112 46774 44151 4175666 3 1 8 7 110 2 6 2 2 410 9 2 1 2 255 5 4 5 51 6 3 8 62 4 1 9 8101 1 1 1 1001 1 1 1001 1 11 1 1 1 1 1 2001 1 1 11 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$$$. Каждый человек получает свои куски торта, и ни один кусок не является общим для двух или более человек.
Можно показать, что для третьего набора входных данных невозможно раздать кусочки торта таким образом, чтобы удовлетворить заданным условиям.
Название |
---|