问题 I: Operation Hope

Little Q is playing an RPG online game. In this game, there are $n$ characters labeled by $1,2,\dots ,n$. The $i$-th character has three types of quotas:

• ai - The maximum points of damage he can achieve in $15$ seconds.
• bi - The maximum points of damage he can achieve in $40$ seconds.
• ci - The maximum points of damage he can achieve in $120$ seconds.

You are the team leader working for the new balance between these $n$ characters, aiming at bringing hope to the weak characters. For each character, your teammates have made a plan to strengthen some skills such that the three quotas may be increased as a result. Note that it is not allowed to weaken characters, because it will make their owners upset.

To make a perfect balance, you need to accept some plans and deny others such that the gap between all the $n$ characters is minimized. Note that a plan can only be entirely accepted or entirely denied. Here, the gap is defined as max(maxai−minai,maxbi−minbi,maxci−minci)

The first line contains a single integer $T$ ($1\le T\le 100$), the number of test cases. For each test case:

The first line contains a single integer $n$ ($1\le n\le 100,000$), denoting the number of characters.

In the next $n$ lines, the $i$-th line contains six integers ai, bi, ci, ai′, bi′ and ci′ (1≤ai≤ai′≤1e9, 1≤bi≤bi′≤1e9, 1≤ci≤ci′≤1e9), describing the quotas of the $i$-th character now and in plan.

It is guaranteed that the sum of all $n$ is at most 500,000

1
2
1 1 1 2 3 5
2 4 3 7 5 8

2