E. Разделение на клики
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два целых числа, $$$n$$$ и $$$k$$$. Рассмотрим граф на $$$n$$$ вершинах, пронумерованных от $$$1$$$ до $$$n$$$, в котором изначально нет ребер.

Вам нужно назначить каждой вершине число; пусть $$$a_i$$$ — число, назначенное вершине $$$i$$$. Все $$$a_i$$$ должны быть различными целыми числами от $$$1$$$ до $$$n$$$.

После того как вы назначили числа для вершин, вы добавляете в граф ребра. Для пары вершин $$$(i, j)$$$ добавляется ребро между ними, если $$$|i - j| + |a_i - a_j| \le k$$$.

Ваша цель — создать граф, который можно разбить на минимально возможное (для заданных значений $$$n$$$ и $$$k$$$) количество клик. Каждая вершина графа должна принадлежать ровно одной клике. Напомним, что клика — это такое множество вершин, что каждая пара вершин в этом множестве соединена ребром.

Поскольку BledDest не особо подтянул свои навыки программирования, он не может решить задачу «дан граф, разбейте его на минимальное количество клик». Поэтому мы также просим вас вывести само разбиение.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1600$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 40$$$; $$$1 \le k \le 2n$$$).

Выходные данные

Для каждого набора входных данных выведите три строки:

  • первая строка должна содержать $$$n$$$ различных целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — значения, которые вы назначаете вершинам;
  • вторая строка должна содержать одно целое число $$$q$$$ ($$$1 \le q \le n$$$) — количество клик, на которые вы разбиваете граф;
  • третья строка должна содержать $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le q$$$) — разбиение графа на клики. Где две вершины $$$u$$$ и $$$v$$$ в одной клике, если $$$c_u = c_v$$$.

Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
3
2 3
5 4
8 16
Выходные данные
2 1
1
1 1
3 1 5 2 4
2
1 1 2 1 2
1 2 3 4 5 6 7 8
1
1 1 1 1 1 1 1 1