题目描述

芙兰朵露有若干个骰子，每个骰子有固定数量的面，每个面标注一个数字。当两个骰子进行 PK 时，随机掷出各自的一个面，点数更大的一方获胜（不会出现平局）。若两个骰子 PK 时，记 \(A\) 骰子掷出的点数大于 \(B\) 骰子的概率为 \(P_1\)， \(B\) 骰子掷出的点数大于 \(A\) 骰子的概率为 \(P_2\)，若满足 \(P_1 \gt P_2\)，则称 \(A\) 骰子比 \(B\) 骰子厉害。

她发现了一个有趣的循环劣势现象：存在一组骰子，其中没有绝对最强的骰子，而是形成闭环的胜负关系。例如：

• \(4\) 个 \(6\) 面骰子的数字分布为： \(1\) 号骰子： \(\{0, 0, 4, 4, 4, 4\}\)， \(2\) 号骰子： \(\{1, 1, 1, 5, 5, 5\}\)， \(3\) 号骰子： \(\{2, 2, 2, 2, 6, 6\}\)， \(4\) 号骰子： \(\{3, 3, 3, 3, 3, 3\}\)
• 两两 PK 结果： \(1\) 号输给 \(2\) 号、 \(2\) 号输给 \(3\) 号、 \(3\) 号输给 \(4\) 号、 \(4\) 号输给 \(1\) 号，形成 \(1→2→3→4→1\) 的循环劣势。

现在，她有一个问题，如果有 \(n\) 个有 \(k\) 面的骰子，每个骰子上可标注的数字范围是 \(0\sim m\)。她想知道你是否能构造出这样的一个满足循环劣势的方案，即使得 \(1\) 号骰子输给 \(2\) 号骰子， \(2\) 号骰子输给 \(3\) 号骰子， \(\dots\)， \(n-1\) 号骰子输给 \(n\) 号骰子， \(n\) 号骰子输给 \(1\) 号骰子。同时，每个数字仅能出现在至多一个骰子上，即任意两个骰子进行 pk 时不可能出现平局的情况，并且一个骰子上最多只会有两种不同的数字。此外，她还想让你找到这样方案里面最小字典序的方案，使得结果便于观察。

最小字典序方案：将 \(1\) 号到 \(n\) 号骰子的数字按顺序拼接成一个长度为 \(n \times k\) 的序列，该序列需是所有满足循环胜负条件的方案中字典序最小的，即从左到右找到第一个位置 \(pos\)，使得 \(A [pos] ≠ B [pos]\)；若此时 \(A [pos] < B [pos]\)，则称方案 \(A\) 的字典序小于方案 \(B\)。

输入格式

第一行一个正整数 \(T\) 表示数据组数。

对于每组数据：

输入三个用空格分隔的正整数 \(n\)， \(m\)， \(k\)，分别表示骰子的数量，可标注的数字范围，骰子的面数。

\(1 \le T \le 10\)

对于每组测试数据：

满足 \(3 \le n \le 10^5, 3 \le k \le 10^5, 3 \le m \le 10^9\), 且 \(9 \le n \times k \le 2 \times 10 ^5\)，保证解一定存在。

输出格式

对于每组测试数据：

输出一行，包含 \(n×k\) 个用空格分隔的整数，依次为 \(1\) 号骰子的 \(k\) 个数字、 \(2\) 号骰子的 \(k\) 个数字、……、 \(n\) 号骰子的 \(k\) 个数字。

样例输入

1
3 4 3

样例输出

0 3 3 1 1 4 2 2 2

提示

这个方案的第一个骰子为 \([0, 3, 3]\),第二个骰子为 \([1, 1, 4]\)，第三个骰子为 \([2, 2, 2]\),可以证明这是所有满足要求的方案中字典序最小的。