给你两个整数,$$$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$$$) — 将图划分为派系。如果 $$$c_u = c_v$$$,则两个顶点 $$$u$$$ 和 $$$v$$$ 位于同一簇中。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 2 3 5 4 8 16
输出 #1
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