题目描述

Alice、Bob 和 Carol 参加了一场比赛。

比赛一共有 $n$ 局。Alice、Bob、Carol 在第 $i$ 局的得分分别为 $a_i$、$b_i$、$c_i$。

Alice 发明了一个称为 胜利区间 的指标。对于 Alice 来说，一个区间 $[l,r]$ 是胜利区间，当且仅当在 $l \le i \le r$ 的场次中，Alice 总得分不低于另外两人（Bob 和 Carol）分别的总得分。即 $\sum_{i=l}^r a_i \ge \max\{\sum_{i=l}^r b_i, \sum_{i=l}^r c_i\}$。

Alice、Bob 和 Carol 都想知道自己的胜利区间的长度的最大值。但是这个问题被他们交给了你。

输入格式

第一行一个正整数 $T$，表示询问次数。

接下来 $T$ 组询问，每组询问包含四行。

第一行一个正整数 $n$，表示比赛局数。

接下来三行，每行 $n$ 个整数，分别代表 Alice、Bob、Carol 在各个场次的得分。

输出格式

共 $T$ 行，每行三个整数，分别代表 Alice、Bob、Carol 的胜利区间长度的最大值。

3
6
1 1 4 5 1 4
1 9 1 9 1 0
1 9 2 6 0 8
2
1 1
1 1
1 1
1
3
2
1

1 5 6
2 2 2
1 0 0

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 10$，$1 \le n \le 500$；
• 对于另外 $30\%$ 的数据，对于所有的 $1 \le i \le n$，$b_i = c_i$；
• 对于 $100\%$ 的数据，$1 \le T \le 2 \cdot 10^4$，$1 \le n, \sum n \le 2 \cdot 10^5$，$0 \le a_i,b_i,c_i \le 10^9$。