Problem Description

After the winter break, Little I returned to school and found that he had forgotten the password of his bike lock, so he asks you for help.

The combination lock on Little I’s bike has $n$ dials, and each dial has $k$ ($k \leq 4$) positions. Each position on the lock contains a positive integer. The positive integer on the $i$-th position of the $j$-th dial is $a _ {i, j}$.

(An example of a lock, where $k = n = 3$. Each column represents one dial, and the positions on a dial are numbered from top to bottom.)

You may rotate each dial any number of times (possibly zero). Each time you rotate a dial once, its positions perform a cyclic shift. Formally, rotating the $j$-th dial once moves the number on the $i$-th position of the $j$-th dial to position $((i \bmod k) + 1)$, while other dials do not change.

(An example of rotating a dial: rotating the second dial of the lock on the left once yields the lock on the right.)

To make it easier to remember, when setting the password, Little I wants the numbers in the same row to be as close as possible. Formally, for $1 \leq i \leq k$, define the looseness of row $i$ of the lock as

$$c(i) = \max \limits _ {j = 1} ^ n a _ {i, j} - \min \limits _ {j = 1} ^ n a _ {i, j}$$

Also define the looseness of the entire lock as

$$C = \max \limits _ {1 \leq i \leq k} c(i)$$

Since an unlockable state is required to make $C$ as small as possible, Little I wants you to find the minimum possible value of $C$.

Input Format

This problem contains multiple test cases. The problem guarantees that all test cases within the same test point have the same $k$.

The first line contains two positive integers $T, k$, representing the number of test cases and the number of positions on each dial.

Then there are $T$ test cases. Each test case is as follows:

The first line contains a positive integer $n$, representing the number of dials.

The next $k$ lines each contain $n$ positive integers, where the $j$-th integer in the $i$-th line, $a _ {i,j}$, represents the number on the $i$-th position of the $j$-th dial.

Note that in the input matrix, each column corresponds to a dial, not each row.

Output Format

For each test case, output one line containing one integer, which is the minimum value of $C$ among all possible choices.

2 3
3
1 2 1
2 3 2
3 1 3
2
1 2
2 1
1 2

0
1

见选手目录下的 lock/lock2.in。

见选手目录下的 lock/lock2.ans。

见选手目录下的 lock/lock3.in。

见选手目录下的 lock/lock3.ans。

见选手目录下的 lock/lock4.in。

见选手目录下的 lock/lock4.ans。

见选手目录下的 lock/lock5.in。

见选手目录下的 lock/lock5.ans。

Hint

[Sample 1 Explanation]

The first sample corresponds to the example in the statement. After rotating the second dial once, each dial becomes $\{1, 2, 3\}$, and the looseness is $0$. It is easy to prove that the looseness cannot be smaller than $0$ anyway, so the output is $0$.

The following four samples correspond to the cases $k = 1, 2, 3, 4$ respectively, and the values of $n$ in the samples have a certain gradient.

[Constraints]

Let $\sum n$ be the sum of $n$ over all test cases within one test point.

For all data, it is guaranteed that $1 \leq T$, $1 \leq k \leq 4$, $1 \leq a _ {i ,j} \leq 3 \times 10 ^ 4$.

This problem is divided into two types of test points.

The first type has twelve test points. It is guaranteed that $k \leq 3$, $n \leq 5 \times 10 ^ 4$, $\sum n \leq 1.5 \times 10 ^ 5$.

Test Point ID	$n \leq$	$\sum n \leq$	$k =$
$1$	$20$	$100$	$1$
$2$	$5 \times 10 ^ 4$	$1.5 \times 10 ^ 5$
$3$	$20$	$100$	$2$
$4$	$100$	$1000$
$5$	$2000$	$10 ^ 4$
$6$	$5 \times 10 ^ 4$	$1.5 \times 10 ^ 5$
$7$	$10$	$50$	$3$
$8$	$50$	$500$
$9$	$300$	$3000$
$10$	$3000$	$2 \times 10 ^ 4$
$11$	$3 \times 10 ^ 4$	$1.2 \times 10 ^ 5$
$12$	$5 \times 10 ^ 4$	$1.5 \times 10 ^ 5$

The second type has eight test points. It is guaranteed that $k = 4$, $n \leq 10 ^ 4$, $\sum n \leq 3 \times 10 ^ 4$.

Test Point ID	$n \leq$	$\sum n \leq$	$k =$
$13$	$10$	$50$	$4$
$14$	$50$	$500$
$15$	$200$	$2000$
$16$	$500$	$4000$
$17$	$2500$	$10 ^ 4$
$18$	$5000$	$2 \times 10 ^ 4$
$19$	$10 ^ 4$	$3 \times 10 ^ 4$
$20$

[Postscript]

After you finally managed to compute the value of $C$, Little I tells you that he has already called a locksmith and used a hammer to brute-force it. After much persuasion, Little I promises that in the future he will not use a combination lock with at least ten thousand dials when locking his bike.

Translated by ChatGPT 5