/ 
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