CF1256C.Platforms Jumping

There is a river of width $n$. The left bank of the river is cell $0$ and the right bank is cell $n + 1$ (more formally, the river can be represented as a sequence of $n + 2$ cells numbered from $0$ to $n + 1$). There are also $m$ wooden platforms on a river, the $i$-th platform has length $c_i$ (so the $i$-th platform takes $c_i$ consecutive cells of the river). It is guaranteed that the sum of lengths of platforms does not exceed $n$.

You are standing at $0$ and want to reach $n+1$ somehow. If you are standing at the position $x$, you can jump to any position in the range $[x + 1; x + d]$. However you don't really like the water so you can jump only to such cells that belong to some wooden platform. For example, if $d=1$, you can jump only to the next position (if it belongs to the wooden platform). You can assume that cells $0$ and $n+1$ belong to wooden platforms.

You want to know if it is possible to reach $n+1$ from $0$ if you can move any platform to the left or to the right arbitrary number of times (possibly, zero) as long as they do not intersect each other (but two platforms can touch each other). It also means that you cannot change the relative order of platforms.

Note that you should move platforms until you start jumping (in other words, you first move the platforms and then start jumping).

For example, if $n=7$, $m=3$, $d=2$ and $c = [1, 2, 1]$, then one of the ways to reach $8$ from $0$ is follow:

The first example: $n=7$.

有一条宽度为 $n$ 的河流。河流的左岸是第 $0$ 号格子，右岸是第 $n + 1$ 号格子（更准确地说，整条河流可表示为编号从 $0$ 到 $n + 1$ 的共 $n + 2$ 个格子组成的序列）。河上还有 $m$ 块木制平台，其中第 $i$ 块平台长度为 $c_i$（即它占据河流中 $c_i$ 个连续的格子）。保证所有平台长度之和不超过 $n$。

你起始于位置 $0$，希望以某种方式到达位置 $n+1$。若你当前位于位置 $x$，则你可以跳跃至区间 $[x + 1,\, x + d]$ 内的任意位置。但你不喜水，因此只能跳到属于某块木制平台的格子上。例如，当 $d = 1$ 时，你只能跳到下一个位置（前提是该位置属于某块木制平台）。可假设格子 $0$ 和 $n+1$ 均属于木制平台。

现在的问题是：在允许将任意平台向左或向右移动任意次数（包括零次）的前提下，能否从 $0$ 到达 $n+1$？移动需满足平台之间互不重叠（但可以相邻），且平台的相对顺序不可改变。

注意：你必须先完成所有平台的移动（即确定各平台最终位置），然后才开始跳跃。

例如，当 $n=7$、$m=3$、$d=2$、$c = [1, 2, 1]$ 时，存在一种从 $0$ 到达 $8$ 的方案，如下图所示：

第一个例子：$n=7$。

The first line of the input contains three integers $n$, $m$ and $d$ ($1 \le n, m, d \le 1000, m \le n$) — the width of the river, the number of platforms and the maximum distance of your jump, correspondingly.

The second line of the input contains $m$ integers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n, \sum\limits_{i=1}^{m} c_i \le n$), where $c_i$ is the length of the $i$-th platform.

输入的第一行包含三个整数 $n$、$m$ 和 $d$（$1 \le n, m, d \le 1000$，且 $m \le n$），分别表示河流的宽度、平台的数量以及你单次跳跃的最大距离。

输入的第二行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \le c_i \le n$，且 $\sum\limits_{i=1}^{m} c_i \le n$），其中 $c_i$ 表示第 $i$ 个平台的长度。

If it is impossible to reach $n+1$ from $0$, print NO in the first line. Otherwise, print YES in the first line and the array $a$ of length $n$ in the second line — the sequence of river cells (excluding cell $0$ and cell $n + 1$).

If the cell $i$ does not belong to any platform, $a_i$ should be $0$. Otherwise, it should be equal to the index of the platform ($1$-indexed, platforms are numbered from $1$ to $m$ in order of input) to which the cell $i$ belongs.

Note that all $a_i$ equal to $1$ should form a contiguous subsegment of the array $a$ of length $c_1$, all $a_i$ equal to $2$ should form a contiguous subsegment of the array $a$ of length $c_2$, ..., all $a_i$ equal to $m$ should form a contiguous subsegment of the array $a$ of length $c_m$. The leftmost position of $2$ in $a$ should be greater than the rightmost position of $1$, the leftmost position of $3$ in $a$ should be greater than the rightmost position of $2$, ..., the leftmost position of $m$ in $a$ should be greater than the rightmost position of $m-1$.

See example outputs for better understanding.

如果无法从 $0$ 到达 $n+1$，则在第一行输出 NO。否则，在第一行输出 YES，并在第二行输出长度为 $n$ 的数组 $a$ —— 表示河流中各格子（不包括格子 $0$ 和格子 $n + 1$）所属的平台编号。

若格子 $i$ 不属于任何平台，则 $a_i$ 应为 $0$；否则，$a_i$ 应等于该格子所属平台的编号（从 $1$ 开始编号，平台按输入顺序依次编号为 $1$ 至 $m$）。

注意：所有值为 $1$ 的 $a_i$ 必须构成数组 $a$ 中一个长度为 $c_1$ 的连续子段；所有值为 $2$ 的 $a_i$ 必须构成数组 $a$ 中一个长度为 $c_2$ 的连续子段；……；所有值为 $m$ 的 $a_i$ 必须构成数组 $a$ 中一个长度为 $c_m$ 的连续子段。此外，$a$ 中数字 $2$ 的最左位置必须严格大于数字 $1$ 的最右位置，数字 $3$ 的最左位置必须严格大于数字 $2$ 的最右位置，……，数字 $m$ 的最左位置必须严格大于数字 $m-1$ 的最右位置。

参见样例输出以获得更清晰的理解。

Consider the first example: the answer is $[0, 1, 0, 2, 2, 0, 3]$. The sequence of jumps you perform is $0 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 7 \rightarrow 8$.

Consider the second example: it does not matter how to place the platform because you always can jump from $0$ to $11$.

Consider the third example: the answer is $[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]$. The sequence of jumps you perform is $0 \rightarrow 5 \rightarrow 6 \rightarrow 11$.

考虑第一个例子：答案为 $[0, 1, 0, 2, 2, 0, 3]$。你执行的跳跃序列为 $0 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 7 \rightarrow 8$。

考虑第二个例子：平台如何放置无关紧要，因为你总能从 $0$ 直接跳到 $11$。

考虑第三个例子：答案为 $[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]$。你执行的跳跃序列为 $0 \rightarrow 5 \rightarrow 6 \rightarrow 11$。