{"raw_statement":[{"iden":"statement","content":"寒假过后，小 I 回到学校，发现自己忘记了自行车锁的密码，于是请你帮忙。\n\n小 I 自行车上的密码锁有 $n$ 个拨圈，每个拨圈有 $k$（$k \\leq 4$）格。密码锁上的每一格都包含一个正整数，其中第 $j$ 个拨圈的第 $i$ 格上的正整数为 $a _ {i, j}$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/0owivo0l.png)\n\n（一个锁的例子，其中 $k = n = 3$，每列表示一个拨圈，拨圈的格子从上往下编号。）\n\n你可以对每个拨圈拨若干次（也可以不拨），每拨一次拨圈，它的格子就会进行一次轮换。形式化地，拨第 $j$ 个拨圈一次，则会让第 $j$ 个拨圈上第 $i$ 格的数字移动到第 $((i \\bmod k) + 1)$ 格，其他拨圈不动。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9d3g6b74.png)\n\n（一个拨动拨圈的例子，对左侧的锁拨一次第二个拨圈得到右侧的锁。）\n\n为了方便记忆，小 I 设定密码时要求同一行上的数字尽可能靠近。\n形式化地，对于 $1 \\leq i \\leq k$，定义密码锁第 $i$ 行的松散度为\n\n$$\nc(i) = \\max \\limits _ {j = 1} ^ n a _ {i, j} - \\min \\limits _ {j = 1} ^ n a _ {i, j} \n$$\n\n同时定义整个密码锁的松散度为\n\n$$\nC = \\max \\limits _ {1 \\leq i \\leq k} c(i)\n$$\n\n因为能开锁的状态满足 $C$ 尽可能小，因此小 I 希望你找出最小的 $C$ 值。"},{"iden":"input","content":"**本题有多组测试数据，题目保证一个测试点中所有测试数据的 $k$ 相同。**\n\n第一行包含两个正整数 $T, k$，分别表示测试数据组数和密码锁拨圈上的格数。\n\n接下来一共 $T$ 组数据，每组数据格式如下：\n\n第一行包含一个正整数 $n$，表示拨圈数。\n\n接下来 $k$ 行，每行包含 $n$ 个正整数，其中第 $i$ 行第 $j$ 个整数 $a _ {i,j}$ 表示密码锁第 $j$ 个拨圈上第 $i$ 格对应的数字。\n\n**注意输入的矩阵中每一列对应一个拨圈，而非每一行对应一个拨圈。**"},{"iden":"output","content":"对于每组数据，输出一行包含一个整数，表示所有方案中 $C$ 的最小值。"},{"iden":"note","content":"**【样例 1 解释】**\n\n第一组样例对应题目描述中的例子。\n在拨第二个拨圈一次后，每个拨圈都是 $\\{1, 2, 3\\}$，此时松散度为 $0$。\n容易证明无论如何松散度都不可能小于 $0$，因此输出 $0$。\n\n以下四个样例分别对应 $k = 1, 2, 3, 4$ 的情况，且样例中 $n$ 的取值有一定梯度。\n\n**【数据范围】**\n\n设 $\\sum n$ 为一个测试点中所有测试数据的 $n$ 的和。\n\n对于所有数据，保证 $1 \\leq T$，$1 \\leq k \\leq 4$，$1 \\leq a _ {i ,j} \\leq  3 \\times 10 ^ 4$。\n\n\n本题分为两类测试点。\n\n\n第一类测试点共有十二个，保证 $k \\leq 3$，$n \\leq 5 \\times 10 ^ 4$，$\\sum n \\leq 1.5 \\times 10 ^ 5$。\n\n| 测试点编号 | $n \\leq$ | $\\sum n \\leq $ | $k = $ |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $20$ | $100$ | $1$ |\n| $2$ | $5 \\times 10 ^ 4$ | $1.5 \\times 10 ^ 5$ | $1$ |\n| $3$ | $20$ | $100$ | $2$ |\n| $4$ | $100$ | $1000$ | $2$ |\n| $5$ | $2000$ | $10 ^ 4$ | $2$ |\n| $6$ | $5 \\times 10 ^ 4$ | $1.5 \\times 10 ^ 5$ | $2$ |\n| $7$ | $10$ | $50$ | $3$ |\n| $8$ | $50$ | $500$ | $3$ |\n| $9$ | $300$ | $3000$ | $3$ |\n| $10$ | $3000$ | $2 \\times 10 ^ 4$ | $3$ |\n| $11$ | $3 \\times 10 ^ 4$ | $1.2 \\times 10 ^ 5$ | $3$ |\n| $12$ | $5 \\times 10 ^ 4$ | $1.5 \\times 10 ^ 5$ | $3$ |\n\n第二类测试点共有八个，保证 $k = 4$，$n \\leq 10 ^ 4$，\n$\\sum n \\leq 3 \\times 10 ^ 4$。\n\n| 测试点编号 | $n \\leq$ | $\\sum n \\leq $ | $k = $ |\n| :----------: | :----------: | :----------: | :----------: |\n| $13$ | $10$ | $50$ | $4$ |\n| $14$ | $50$ | $500$ | $4$ |\n| $15$ | $200$ | $2000$ | $4$ |\n| $16$ | $500$ | $4000$ | $4$ |\n| $17$ | $2500$ | $10 ^ 4$ | $4$ |\n| $18$ | $5000$ | $2 \\times 10 ^ 4$ | $4$ |\n| $19$ | $10 ^ 4$ | $3 \\times 10 ^ 4$ | $4$ |\n| $20$ | $10 ^ 4$ | $3 \\times 10 ^ 4$ | $4$ |\n\n**【后记】**\n\n你花了九牛二虎之力算出 $C$ 的值之后，小 I 却告诉你他已经找开锁师傅用锤子暴力破解了。在你的百般劝说下，小 I 承诺以后锁车不用有大于等于一万个拨圈的密码锁。"}],"translated_statement":null,"sample_group":[["2 3\n3\n1 2 1\n2 3 2\n3 1 3\n2\n1 2\n2 1\n1 2","0\n1"],["见选手目录下的 lock/lock2.in。","见选手目录下的 lock/lock2.ans。"],["见选手目录下的 lock/lock3.in。","见选手目录下的 lock/lock3.ans。"],["见选手目录下的 lock/lock4.in。","见选手目录下的 lock/lock4.ans。"],["见选手目录下的 lock/lock5.in。","见选手目录下的 lock/lock5.ans。"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}