F. Сыграем в Шляпу?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Шляпа — игра на скоростное объяснение/отгадывание слов. Это весело. Попробуйте! В этой задаче речь идёт о варианте игры, когда игроки сидят за столом и каждый играет за себя.

$$$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$$$), кто должен играть за этим столом.

Если искомых расписаний несколько, то выведите любое из них. Можно показать, что искомое решение обязательно существует.

Вы можете выводить дополнительные пустые строки для разделения ответов на разные наборы входных данных.

Пример
Входные данные
3
5 2 2
8 3 1
2 1 3
Выходные данные
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