P4753 River Jumping

There is a river of width $N$. Little D is on the bank at coordinate $0$. He wants to reach the bank at coordinate $N$ and then return to coordinate $0$. Before reaching the bank at coordinate $N$, Little D can only jump to positions with larger coordinates. After reaching the bank at coordinate $N$, Little D can only jump to positions with smaller coordinates. There are $M$ rocks in the river. Little D hopes to land on each rock exactly once. Because Little D can jump very far, his jump length has a lower bound $S$ but no upper bound. Now determine whether he can achieve his goal.

The first line contains three integers $N, M, S$, representing the width of the river, the number of rocks, and the lower bound of the jump length. The second line contains $M$ integers, representing the coordinates of the $M$ rocks: $w_1, w_2, \cdots, w_N$. It is guaranteed that $\{w_i\}$ is a strictly increasing sequence.

If Little D can achieve his goal, output `YES` on the first line, and output $M + 2$ numbers on the second line, in order, representing the indices of the stones that Little D lands on. In particular, the bank at coordinate $0$ has index $0$, and the bank at coordinate $N$ has index $M + 1$. If there are multiple solutions, you may output any one of them. If Little D cannot achieve his goal, output `NO` on the first line.

For all testdata, it is guaranteed that $1 \le N, S \le 100000$, $0 \le M < N$, and $1 \le w_i < N$. Translated by ChatGPT 5