3698 - 最慢的快排

Description

小 nod 新学了快速排序，并且学会了用 random 函数获取随机中枢避免最坏复杂度。代码如下：

void Qsort(int a[], int low, int high) { if(low >= high) return; int first = low; int last = high; int key_index = (rand() % (high - low + 1)) + low; swap(a[first], a[key_index]); int key = a[first]; while(first < last) { while(first < last && a[last] >= key) --last; a[first] = a[last]; while(first < last && a[first] <= key) ++first; a[last] = a[first]; } a[first] = key; Qsort(a, low, first - 1); Qsort(a, first + 1, high); }

号称这份代码跑得比谁都快。夹克老爷为了教育他，构造了大小为 k 的数组 r，使得快排开始后，第 i 次调用 rand 函数时返回的是 r[i%k]（这里 i 从 0 开始，即简单地按从前往后循环使用 r 数组）。
给出 r 数组中的 k 个数，你能构造一个 1~N 的排列，让测试机上运行的快排代码递归调用深度最大吗？（Qsort 函数的递归调用深度最大，不考虑尾递归优化）。
输出递归深度最大的排列中字典序最小的那个排列。
例如 N=3, k=1, r=[0]：每次选择第 0 个数字作为枢轴，最大递归 3 层，(1,2,3)、(3,2,1)、(3,1,2) 等都符合，其中字典序最小的是 (1,2,3)，答案为 1 2 3。

Input

第一行两个整数 N, K（1 <= N <= 50000, 1 <= K <= 50000）。
第 2 ~ K+1 行：每行 1 个数，对应数组 r 中的元素（0 <= r[i] <= 10^9）。

Output

一行 N 个整数，1~N 的一个排列，使得上述快排代码递归深度最大，输出其中字典序最小的那个排列。

Examples

Input

3 1
0

Output

1 2 3

Input

3 1
1

Output

1 3 2

Input

4 2
1
2

Output

1 4 3 2

Hint

每次中枢选中当前段的最大值或最小值可只排除一个数字，从而得到最大递归深度。为使字典序最小，中枢位置确定后：若该位置左边还有未填数字则此处放当前最大值、把最小值留给更靠左的位置，否则放最小值。注意正确复刻题面代码中与 first 交换、以及回填枢轴的逻辑。（本题评测数据规模较小 N<=9）

Source

51nod 1377

Time Limit	1 second
Memory Limit	128 MB
提交次数	0
通过次数	0