Let's Play the Hat?

题意翻译

# 题目描述 The Hat是一个快速解释/猜测单词的游戏(类似于Alias)。在这道题中，我们所讨论的是一种游戏变体，即玩家坐在桌旁，每个人都单独玩游戏。 有 $n$ 个人聚集在一个有 $m$ 张桌子( $n \ge m \times 2$ )的房间里。他们想玩 $k$ 次 The Hat。$k$ 次游戏将在这些桌子上进行，每个人都会玩 $k$ 次游戏。 这些玩家被分配到这些桌子上。每个玩家可以在不同的桌子上玩，但每局游戏每个玩家只能在一张桌子上玩。 玩家们希望拥有“公平”的游戏顺序。出于这个原因，他们正在寻找一个方案，要求如下: - 在任意一场游戏中，所有桌子都有 $\lfloor \dfrac{n}{m} \rfloor$ 或 $\lceil \dfrac{n}{m} \rceil$ 个玩家。不同的桌子有不同数量的玩家，这些玩家可以玩不同的游戏。 - 每个玩家都有一个值 $b_i$，它表示第 $i$ 个玩家和 $\lceil \dfrac{n}{m} \rceil$ 个玩家在一张桌子上玩游戏的次数。任意两个玩家的 $b_i$ 值相差不会超过 $1$。换句话说，对于任意两个玩家 $i,j$，满足 $|b_i-b_j| \leq 1$。 我们称有 $\lfloor \dfrac{n}{m} \rfloor$ 个玩家的桌子为“小桌子”，称有 $\lceil \dfrac{n}{m} \rceil$ 个玩家的桌子为“大桌子”。 例如，$n=5,m=2,k=2$，那么根据第一项要求，每张桌子上应该有 $2$ 或 $3$ 名玩家。考虑这些游戏顺序： - 第一局：玩家 $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]$ (任意两个值的差都不超过 $1$)。 为 $n$ 个玩家找到所有“公平”的顺序，如果他们玩 $k$ 次游戏，在 $m$ 张桌子上。 # 输入格式 第一行一个整数 $t(1 \leq t \leq 10^4)$，表示数据组数。 接下来 $t$ 行，每行三个整数 $n,m,k(2 \leq n \leq 2 \times 10^5,1 \leq m \leq \lfloor \dfrac{n}{2} \rfloor,1 \leq k \leq 10^5)$，分别表示玩家个数，桌子个数以及游戏次数。 保证所有测试用例的 $n \times k$ 之和不超过 $2 \times 10^5$。 # 输出格式 对于每组数据，输出 $k$ 块矩阵，每块矩阵有 $m$ 行。每一块矩阵表示一次游戏，共有 $m$ 张桌子，用一行表示一张桌子，每行先输出这张桌子的玩家数，再输出这些玩家。每组数据 如果有多个“公平”的顺序，那么输出任意一个。保证至少有一个有效的解。

题目描述

The Hat is a game of speedy explanation/guessing words (similar to Alias). It's fun. Try it! In this problem, we are talking about a variant of the game when the players are sitting at the table and everyone plays individually (i.e. not teams, but individual gamers play). $ n $ people gathered in a room with $ m $ tables ( $ n \ge 2m $ ). They want to play the Hat $ k $ times. Thus, $ k $ games will be played at each table. Each player will play in $ k $ games. To do this, they are distributed among the tables for each game. During each game, one player plays at exactly one table. A player can play at different tables. Players want to have the most "fair" schedule of games. For this reason, they are looking for a schedule (table distribution for each game) such that: - At any table in each game there are either $ \lfloor\frac{n}{m}\rfloor $ people or $ \lceil\frac{n}{m}\rceil $ people (that is, either $ n/m $ rounded down, or $ n/m $ rounded up). Different numbers of people can play different games at the same table. - Let's calculate for each player the value $ b_i $ — the number of times the $ i $ -th player played at a table with $ \lceil\frac{n}{m}\rceil $ persons ( $ n/m $ rounded up). Any two values of $ b_i $ must differ by no more than $ 1 $ . In other words, for any two players $ i $ and $ j $ , it must be true $ |b_i - b_j| \le 1 $ . For example, if $ n=5 $ , $ m=2 $ and $ k=2 $ , then at the request of the first item either two players or three players should play at each table. Consider the following schedules: - First game: $ 1, 2, 3 $ are played at the first table, and $ 4, 5 $ at the second one. The second game: at the first table they play $ 5, 1 $ , and at the second — $ 2, 3, 4 $ . This schedule is not "fair" since $ b_2=2 $ (the second player played twice at a big table) and $ b_5=0 $ (the fifth player did not play at a big table). - First game: $ 1, 2, 3 $ are played at the first table, and $ 4, 5 $ at the second one. The second game: at the first table they play $ 4, 5, 2 $ , and at the second one — $ 1, 3 $ . This schedule is "fair": $ b=[1,2,1,1,1] $ (any two values of $ b_i $ differ by no more than $ 1 $ ). Find any "fair" game schedule for $ n $ people if they play on the $ m $ tables of $ k $ games.

输入输出格式

输入格式

The first line of the input contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the test. Each test case consists of one line that contains three integers $ n $ , $ m $ and $ k $ ( $ 2 \le n \le 2\cdot10^5 $ , $ 1 \le m \le \lfloor\frac{n}{2}\rfloor $ , $ 1 \le k \le 10^5 $ ) — the number of people, tables and games, respectively. It is guaranteed that the sum of $ nk $ ( $ n $ multiplied by $ k $ ) over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case print a required schedule — a sequence of $ k $ blocks of $ m $ lines. Each block corresponds to one game, a line in a block corresponds to one table. In each line print the number of players at the table and the indices of the players (numbers from $ 1 $ to $ n $ ) who should play at this table. If there are several required schedules, then output any of them. We can show that a valid solution always exists. You can output additional blank lines to separate responses to different sets of inputs.

输入输出样例

输入样例 #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