E - K Different Values Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

長さ N の整数列 A=(A_1,A_2,\cdots,A_N),及び整数 K が与えられます.

以下の条件を両方満たす整数列 x を作ることを考えます.

  • 各整数 i (1 \leq i \leq N) について,x はちょうど A_i 個の i を含む. また逆に,それ以外の整数を含まない.
  • x の中で連続するどの K 個を見ても,その K 個の値はすべて異なる.

条件を満たす x を作ることが可能かどうか判定し,可能な場合は条件を満たす中で辞書順最小の x を求めてください.

制約

  • 2 \leq K \leq N \leq 500
  • 1 \leq A_i
  • \sum_{1 \leq i \leq N} A_i \leq 200000
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる.

N K
A_1 A_2 \cdots A_N

出力

条件を満たす数列 x が作ることが不可能な場合,-1 と出力せよ. 可能な場合,辞書順最小の x を出力せよ.


入力例 1

3 3
2 2 1

出力例 1

1 2 3 1 2

x=(1,2,3,1,2),(2,1,3,2,1) の二つが条件を満たし,その中で辞書順最小の (1,2,3,1,2) が答えになります.


入力例 2

3 2
2 1 2

出力例 2

1 2 3 1 3

入力例 3

3 3
1 3 3

出力例 3

-1

Score : 800 points

Problem Statement

Given are a sequence of N integers A=(A_1,A_2,\cdots,A_N) and an integer K.

Consider making a sequence of integers x that satisfies both of the following conditions.

  • For each integer i (1 \leq i \leq N), x contains exactly A_i occurrences of i. x does not contain other integers.
  • For every way of choosing K consecutive elements from x, their values are all distinct.

Determine whether it is possible to make x that satisfies the conditions. If it is possible, find the lexicographically smallest such x.

Constraints

  • 2 \leq K \leq N \leq 500
  • 1 \leq A_i
  • \sum_{1 \leq i \leq N} A_i \leq 200000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_N

Output

If it is impossible to make a sequence x that satisfies the conditions, print -1. If it is possible, print the lexicographically smallest such x.


Sample Input 1

3 3
2 2 1

Sample Output 1

1 2 3 1 2

Two sequences x=(1,2,3,1,2),(2,1,3,2,1) satisfy the conditions. The lexicographically smaller one, (1,2,3,1,2), is the answer.


Sample Input 2

3 2
2 1 2

Sample Output 2

1 2 3 1 3

Sample Input 3

3 3
1 3 3

Sample Output 3

-1