406302: GYM102348 E Painting The Fence

The fence consists of $$$n$$$ planks, arranged from left to right. Monocarp has $$$m$$$ different types of paint, and the number of planks that can be painted in color $$$i$$$ is $$$a_i$$$ (there's not enough paint to color any more planks). The total amount of paint is just enough to paint exactly $$$n$$$ planks — in other words, the sum of all $$$a_i$$$ is equal to $$$n$$$. Each plank should be painted into exactly one color.

Monocarp has to paint the fence in such a way that the length of every contiguous segment consisting of planks of the same color is not greater than $$$k$$$.

Find a suitable way to paint the fence, or say that it is impossible.

The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ $$$(1 \le n \le 2 \cdot 10^{5}, 1 \le m, k \le n)$$$ — the number of planks in the fence, the number of different colors of paint and the maximum length of a contiguous segment of planks with the same color, respectively.

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_m$$$ $$$(1 \le a_i \le n)$$$, where $$$a_i$$$ is the number of planks that can be painted with color $$$i$$$. The sum of all values of $$$a_i$$$ is equal to $$$n$$$.

If it is impossible to paint the fence in such a way that the length of every contiguous segment consisting of planks of the same color is not greater than $$$k$$$, print $$$-1$$$.

Otherwise print $$$n$$$ integers, $$$i$$$-th of them should be equal to the index of the color of the $$$i$$$-th plank. If there are multiple possible answers, print any of them.

5 2 1
2 3

2 1 2 1 2 

8 2 3
1 7

-1

10 3 2
5 2 3

1 1 3 1 1 2 3 1 2 3 

In the first example the first, third and fifth planks should have color $$$2$$$, and all other planks should have color $$$1$$$.

In the second example it is impossible to paint the fence in the required way, so the answer is $$$-1$$$.