P9120 [Spring Test 2023] Combination Lock.

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$.

**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.**

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

**[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$ | $1$ | | $3$ | $20$ | $100$ | $2$ | | $4$ | $100$ | $1000$ | $2$ | | $5$ | $2000$ | $10 ^ 4$ | $2$ | | $6$ | $5 \times 10 ^ 4$ | $1.5 \times 10 ^ 5$ | $2$ | | $7$ | $10$ | $50$ | $3$ | | $8$ | $50$ | $500$ | $3$ | | $9$ | $300$ | $3000$ | $3$ | | $10$ | $3000$ | $2 \times 10 ^ 4$ | $3$ | | $11$ | $3 \times 10 ^ 4$ | $1.2 \times 10 ^ 5$ | $3$ | | $12$ | $5 \times 10 ^ 4$ | $1.5 \times 10 ^ 5$ | $3$ | 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$ | $4$ | | $15$ | $200$ | $2000$ | $4$ | | $16$ | $500$ | $4000$ | $4$ | | $17$ | $2500$ | $10 ^ 4$ | $4$ | | $18$ | $5000$ | $2 \times 10 ^ 4$ | $4$ | | $19$ | $10 ^ 4$ | $3 \times 10 ^ 4$ | $4$ | | $20$ | $10 ^ 4$ | $3 \times 10 ^ 4$ | $4$ | **[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