Optimal Tower Coverage

You are given a number of factories arranged on a line along with a specified number of air purification towers. Your task is to determine the optimal positions and coverage ranges for the towers such that they can cover the region spanning the factories.

For each test case, you are provided:

• N: the number of factories.
• M: the number of towers.
• A list of N integer coordinates indicating the positions of the factories.

The towers are to be installed on the same line as the factories. When there is exactly one tower (i.e. \(M=1\)), the tower should cover the entire span from the leftmost factory to the rightmost factory. Otherwise, for \(M>1\), you should position the towers in an evenly spaced manner between the positions of the leftmost and rightmost factories. In this case, the position of the \(i^{th}\) tower is computed as:

[ P_i = P_{min} + i \times \frac{P_{max} - P_{min}}{M} \quad \text{for } i = 0, 1, \ldots, M-1, ]

and the range (coverage) of each tower is \(R = \frac{P_{max} - P_{min}}{M}\) (using integer truncation in the final result).

Your output for each test case is a sequence of \(M\) pairs, where each pair consists of the starting position and the range of the tower.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N1 M1
position1 position2 ... positionN₁
N2 M2
position1 position2 ... positionN₂
...
NT MT
position1 position2 ... positionNₜ

Where T is the number of test cases. For each test case, the first line contains two integers: N (the number of factories) and M (the number of towers). This is followed by a line with N integers representing the positions of the factories (which may not be sorted).

outputFormat

For each test case, print a single line to standard output (stdout) containing \(M\) pairs. Each pair consists of two integers: the starting position and the coverage range for a tower. The pairs should be printed in order, separated by a space. For example, if there are two towers, the output line might be:

P₁ R₁ P₂ R₂

## sample

1
5 1
10 20 30 40 50

10 40

</p>