← 返回题目列表

Codeforces · 67/B

B. 排列的恢复

中文机器翻译题面 查看原题

设 A = {a1, a2, ..., an} 为前 n 个自然数 {1, 2, ..., n} 的任意排列。给定一个正整数 k 和另一个序列 B = {b1, b2, ..., bn},其中 bi 是 A 中 = i 处元素左侧的元素 aj 的数量,使得 aj ≥ (i + k)。

例如,如果 n = 5,则可能的 A 为 {5, 1, 4, 2, 3}。对于 k = 2,B 由 {1, 2, 1, 0, 0} 给出。但如果 k = 3,则 B = {1, 1, 0, 0, 0}。

对于两个序列 X = {x1, x2, ..., xn} 和 Y = {y1, y2, ..., yn},令第 i 个元素为第一个满足 xi ≠ yi 的元素。如果 xi < yi,则 X 按字典顺序小于 Y,而如果 xi > yi,则 X 按字典顺序大于 Y。

给定 n、k 和 B,您需要确定字典顺序最小的 A。

输入

第一行包含两个空格分隔的整数 n 和 k (1 ≤ n ≤ 1000, 1 ≤ k ≤ n)。第二行是 n 个整数,指定 B = {b1, b2, ..., bn} 的值。

输出

在单行上打印 A = {a1, a2, ..., an} 的 n 个整数,使得 A 在字典顺序上最小。保证解存在。

示例

输入 #1

5 2
1 2 1 0 0

输出 #1

4 1 5 2 3

输入 #2

4 2
1 0 0 0

输出 #2

2 3 1 4