时间限制： 3.0 秒

空间限制： 512 MB

题目描述

B-树是一种多路平衡树，其中每个节点内存放多个关键码，并且对应多个子节点。具体维护方式查询互联网相关资料或者教材/课件（推荐直接查找邓俊辉《数据结构》）。

在本题中，你需要维护一个 $M$ 阶 B-树，现给定关键码插入序列，序列中的关键码两两不同。在将他们按照先后顺序插入进一个初始无关键码的 $M$ 阶 B-树之后，请你输出该树的层次遍历形式。

输入格式

从标准输入读入数据。

第一次输入两个整数 $n,M$，分别表示插入序列长度和 B-树的阶数。

第二行包含 $n$ 个不同的整数，表示每个插入值。

输出格式

输出到标准输出。

输出若干行，为最终 B-树的层次遍历。具体格式如下：

• 处于同一层的节点在相同的行输出，不同层按照从根节点开始从上到下的顺序输出；
• 每一个节点内的若干个关键码按照 [a1,a2,a3,...,ak] 的形式输出，同一行的节点之间不需要用空格等字符分隔。

具体示范见以下两个样例。

14 3
53 97 36 89 41 75 19 84 77 79 51 23 29 45

[36,53]
[23][45][77,89]
[19][29][41][51][75][79,84][97]

样例 1 解释

具体过程见图示，在插入第 11、12、13 个关键码，以及在样例 1 的基础上插入关键码 87 之后的形态也可以按照图示进行样例调试。

53 5
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 56 60 64 68 72 76 80 84 53 54 55 85 86 87 88 89 90 91 92 93 94 95 96 97 98 73 74 75 57 65 69 58 59 66 99

[64]
[25,52][76,91]
[7,16][34,43][55,58][68,73][85,88][94,97]
[1,4][10,13][19,22][28,31][37,40][46,49][53,54][56,57][59,60][65,66][69,72][74,75][80,84][86,87][89,90][92,93][95,96][98,99]

样例 2 解释

具体过程见图示，在插入第 49、50、51、52 个关键码的形态也可以按照图示进行样例调试。

子任务

对于所有数据，插入序列长度 $n\le 5\times 10^5$，阶数 $M\le 25$ 且一定为奇数，所有关键码保证 $-10^9\le a_i\le 10^9$。

提示

由于本题只有插入操作，因此你只需要完成插入以及上溢处理即可，本题添加了 $M$ 为奇数的限制，从而保证了上溢处理的形态一定唯一。如果你想完整实现下溢和删除操作，请移步普通平衡树进行测试。

来源

改编自 浙大 DSA 7-29 Self-printable B+ Tree