Three-People Contests ~ Multiplex Coder

Problem

Chef is organizing "Three-People Contests" for his nephews.

Alice, Bob, and Charles took part in $�$ contests, where, in the $�^{� ℎ}$ contest, they got $�_{�}$ , $�_{�}$ , and $�_{�}$ points respectively.

For each person, find the longest subarray $[�, �]$ , such that the person gets the first place if we only consider the contests in the range $[�, �]$ . The length of such subarray is $(� - � + 1)$ , or $0$ , if there are no such subarrays.

A person gets first place if the total points they score in these contests are not less than that of any other contestant.

Input Format

The first line of input will contain a single integer $�$ , denoting the number of test cases.
Each test case consists of multiple lines of input.
- The first line of each test case contains one integer $�$ — the number of contests organized by Chef.
- The second line of each test case contains an array of $�$ integers, $�_{1}, �_{2}, \dots, �_{�}$ , the score of Alice in the $�$ contests.
- The third line contains an array of $�$ integers, $�_{1}, �_{2}, \dots, �_{�}$ , the score of Bob in the $�$ contests.
- The fourth line contains an array of $�$ integers, $�_{1}, �_{2}, \dots, �_{�}$ , the score of Charles in the $�$ contests.

Output Format

For each test case, output on a new line, $3$ space-separated integers, answer for Alice, Bob, and Charles in the same order.

Constraints

$1 \leq � \leq 2 \cdot 1 0^{4}$
$1 \leq � \leq 2 \cdot 1 0^{5}$
$0 \leq �_{�}, �_{�}, �_{�} \leq 1 0^{9}$
The sum of $�$ over all test cases won't exceed $2 \cdot 1 0^{5}$ .

Sample 1:

Input

Output

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

4 1 6
4 4 4
2 0 0

Explanation:

Test case $1$ : Alice gets first place in the contests between $� = 3$ and $� = 6$ as she gets $8 + 1 + 3 + 7 = 19$ points, while Bob and Charles get $1 + 1 + 2 + 0 = 4$ and $3 + 9 + 3 + 3 = 18$ points, respectively. The answer for Alice is $6 - 3 + 1 = 4$ .

Bob gets first place in the contest $3$ with score $8$ . Note that in $� = � = 3$ , Charles also gets $8$ points, so they both get first place. The answer for Bob is $3 - 3 + 1 = 1$ .

Charles wins in $� = 1$ and $� = 6$ , as he gets $8 + 8 + 3 + 9 + 3 + 3 = 34$ points, which is not less than $5 + 5 + 8 + 1 + 3 + 7 = 29$ and $0 + 8 + 1 + 1 + 2 + 0 = 12$ . The answer for Charles is $6 - 1 + 1 = 6$ .

Test case $2$ : Everyone has a score of $4$ points. Since the score of each person is not less than the score of other $2$ people, everyone gets the first place. Thus, $� = 1$ and $� = 4$ for everyone. The length of the array is $4 - 1 + 1 = 4$ .