In a sports club, there are 3 groups of players, say A, B and C. Each group has N players. You are the manager of the club and were asked to select 3 players (one from each group) to represent your club in a team tournament. To do this you marked each player with an integer K, representing their compatibility with other players.
The smaller the difference in K (between two players) the more compatible they are, i.e. a player with K = 2 is more compatible with a player whose K = 3 or K = 1, than a player with K = 4.
Now you want to select 3 players (one from each group) such that the range of K of those players in minimum.
PS : Your club is very efficient so everyone in your club is equally skilled :P
Input and Output Specifications
First line of input will contain an integer T. T test cases follows.
First line of each test case contain N, the size of each array.
Next three lines contains N integers in increasing order.
You have to output the minimum range of K possible.
T <= 100
N <= 1000
1 <= K <= 10^9
1 1 2 3 4
2 5 6 9 10
7 8 9 10 11
4 is selected from first group, 5 or 6 from second and 7 from third. The range of K in this case is 3. Any other selection will result in larger range.
Problem Source : Flipkart Interview
Problem Setter : Pushkar Anand
Problem Tester : Jayant Mukherjee