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, \dots, r_a]$、$[l_b, \dots, r_b]$ 和 $[l_c, \dots, 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 \ge \left\lceil \frac{tot}{3} \right\rceil$。

其中 $\lceil \frac{a}{b} \rceil$ 表示向上取整，即大于或等于精确除法结果的最小整数。例如 $\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, \dots, a_n$，表示爱丽丝对每块蛋糕的估值（$1 \le a_i \le 10^6$）。
  • 下一行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示鲍勃对每块蛋糕的估值（$1 \le b_i \le 10^6$）。
  • 下一行包含 $n$ 个整数 $c_1, c_2, \dots, 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$。每个人分得不同的蛋糕块，没有重叠。

可以证明，对于第三个测试用例，无法在满足给定约束的条件下分配蛋糕切片。