Madeline 来到了天空度假山庄,她在这里遇到了长满煤球的道路。这样的路只能经过一次,多次经过就会被煤球腐乳。旅馆老板告诉她离开这里的规则:
整个山庄有 n 个房间,除了初始房间(1 号)外每个房间都有一个草莓,房间两两之间有且仅有一条煤球路连接,每次走了 k 步就会捡起当前房间的草莓,如果当前房间草莓已经被捡起,老板就会把你吃掉。
你需要收集所有的草莓,就可以成功离开这里。
简化题意:
有一个 n 个点的完全图,你需要构造一条从 1 开始长度为 k(n−1) 的路径,每 k 步到达的点互不相同且不为起点。每条边只能被经过一次(正向经过后也不能再反向经过)。
输入格式
一行两个数 n,k ,含义如题面。
输出格式
一行 k(n−1) 个数,表示每一步的终点,输出任意可行解即可。
样例
样例输入 1
3 1
样例输出 1
2 3
样例输入 2
5 2
样例输出 2
2 5 4 2 3 4 1 3
样例解释 2
Madeline 依次在房间 5,2,4,3 捡到草莓后离开山庄。
注意,样例并不满足数据范围限制,只是助于理解题意。
数据范围
对于所有数据,n×k≤1×106,n≥max(2k+15,30) , k≥1。
subtask1(5pts):k≤2
subtask2(20pts):n≥4k2+229
subtask3(20pts):n≥5k+15
subtask4(20pts): k 为 229 或 233 或 114 或 514 。
subtask5(35pts): 无特殊限制