Alice、Bob 和 Charlie 想分享一个切成 $$$n$$$ 块的矩形蛋糕。每个人认为每件作品都有不同的价值。 Alice 认为第 $$$i$$$ 块有价值 $$$a_i$$$,Bob 认为第 $$$b_i$$$ 有价值,Charlie 认为第 $$$c_i$$$ 有价值。
所有$$$a_i$$$、所有$$$b_i$$$ 和所有$$$c_i$$$ 的总和均相同,等于$$$tot$$$。
给定每个人每块蛋糕的价值,您需要给每个人一块连续的蛋糕。换句话说,对于 Alice、Bob 和 Charlie,这些子数组(给每个人的切片)左端和右端的索引可以分别表示为 $$$(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$$$ 代表 Alice 的值 ($$$1 \le a_i \le 10^6$$$)。
下一行 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ 代表 Bob 的值 ($$$1 \le b_i \le 10^6$$$)。
下一行 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ 代表 Charlie 的值 ($$$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$$$,分别是 Alice、Bob 和 Charlie 子数组的起始索引和结束索引($$$1$$$ 索引)。
示例
输入 #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 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$$$) 分配给 Alice,则其总价值为 $$$5$$$,即 $$$\ge 3$$$;子数组 ($$$2$$$,$$$3$$$) 给 Bob,其总价值为 $$$1 + 5 = 6$$$,即 $$$\ge 3$$$;子数组 ($$$4$$$,$$$5$$$) 对于 Charlie 来说,其总价值为 $$$1 + 5 = 6$$$,这也是 $$$\ge 3$$$。每个人都有自己独立的一块蛋糕,没有一块蛋糕是两个或更多人共同的。
可以看出,对于第三个测试用例,不可能以满足给定约束的方式给出蛋糕切片。