The Hat 是一款快速解释/猜词的游戏(类似于 Alias)。很有趣。试试吧!在这个问题中,我们讨论的是游戏的一种变体,即玩家坐在桌子旁,每个人都单独玩(即不是团队,而是个人玩家玩)。
$$$n$$$ 人聚集在一个房间里,房间里有 $$$m$$$ 桌子 ($$$n \ge 2m$$$)。他们想玩帽子 $$$k$$$ 次。因此,每张桌子都会玩 $$$k$$$ 游戏。每个玩家将参加 $$$k$$$ 游戏。
为此,它们被分布在每场比赛的桌子上。在每场比赛中,一名玩家只在一张桌子上玩。玩家可以在不同的牌桌上玩。
玩家希望拥有最“公平”的比赛日程。因此,他们正在寻找一个时间表(每场比赛的桌子分布),以便:
- 每场比赛中的任何牌桌上都有 $$$\lfloor\frac{n}{m}\rfloor$$$ 人或 $$$\lceil\frac{n}{m}\rceil$$$ 人(也就是说,要么 $$$n/m$$$ 向下舍入,要么 $$$n/m$$$ 向上舍入)。不同数量的人可以在同一张桌子上玩不同的游戏。
- 让我们计算每个玩家的值 $$$b_i$$$ — 第 $$$i$$$ 玩家与 $$$\lceil\frac{n}{m}\rceil$$$ 人在牌桌上玩的次数($$$n/m$$$ 向上舍入)。 $$$b_i$$$ 的任何两个值的差异不得超过 $$$1$$$。换句话说,对于任意两个玩家 $$$i$$$ 和 $$$j$$$,它必须为真 $$$|b_i - b_j| \le 1$$$。
例如,如果 $$$n=5$$$、$$$m=2$$$ 且 $$$k=2$$$,则根据第一项的要求,每张牌桌上应有两名玩家或三名玩家进行游戏。考虑以下时间表:
- 第一局游戏:第一张牌桌玩 $$$1, 2, 3$$$,第二张牌桌玩 $$$4, 5$$$。第二场比赛:在第一张桌子上他们玩$$$5, 1$$$,在第二张桌子上玩$$$2, 3, 4$$$。这个时间表并不“公平”,因为$$$b_2=2$$$(第二个玩家在大牌桌上玩了两次)和$$$b_5=0$$$(第五个玩家没有在大牌桌上玩过)。
- 第一局游戏:第一张牌桌玩 $$$1, 2, 3$$$,第二张牌桌玩 $$$4, 5$$$。第二场比赛:在第一张桌子上,他们玩 $$$4, 5, 2$$$,在第二张桌子上,他们玩 $$$1, 3$$$。这个时间表是“公平的”:$$$b=[1,2,1,1,1]$$$($$$b_i$$$ 的任何两个值相差不超过$$$1$$$)。
如果 $$$n$$$ 人在 $$$m$$$ 桌上玩 $$$k$$$ 游戏,请找到任何“公平”的游戏时间表。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
每个测试用例由一行组成,其中包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 2\cdot10^5$$$, $$$1 \le m \le \lfloor\frac{n}{2}\rfloor$$$, $$$1 \le k \le 10^5$$$) —分别是人数、桌子和游戏的数量。
保证所有测试用例的$$$nk$$$($$$n$$$乘以$$$k$$$)总和不超过$$$2\cdot10^5$$$。
输出
对于每个测试用例,打印一个所需的时间表 - 一系列 $$$k$$$ 块,每行 $$$m$$$。每个区块对应一场比赛,区块中的一行对应一张桌子。在每行中打印牌桌上的玩家数量以及应该在该牌桌上玩的玩家的索引(从 $$$1$$$ 到 $$$n$$$ 的数字)。
如果有多个所需的时间表,则输出其中任何一个。我们可以证明,有效的解决方案总是存在的。
您可以输出额外的空行来分隔对不同输入集的响应。
示例
输入 #1
3 5 2 2 8 3 1 2 1 3
输出 #1
3 1 2 3 2 4 5 3 4 5 2 2 1 3 2 6 2 3 3 5 1 3 4 7 8 2 2 1 2 2 1 2 2 1