Songwriter

题意翻译

**题目描述** 安迪是数学家，计算机科学家和作曲家。潜心创作很长时间后，他终于写出了一首他认为是他最好的作品。但是，每位歌手有一个独特的音域，因此可能需要调整。 旋律被定义为$N$个音符的序列（保证$N$为整数）。$A$是安迪创作的原旋律。现在需要把$A$调整成一个新的旋律B，这样对于每个小于$N$的$i$： - 若$A_i<A_{i+1}$，那么$B_i<B_{i+1}$； - 若$A_i=A_{i+1}$，那么$B_i=B_{i+1}$； - 若$A_i>A_{i+1}$，那么$B_i>B_{i+1}$； - $|B_i-B_{i+1}|\le K$，即两个连续音符之间的差不大于$K$。 此外，歌手还要求所有的音符都在她的音域范围内，即对于所有$i$都要求$L\le B_i\le R$。请你帮助安迪找出符合条件的字典序最小的$B$。若存在$j$（$1\le j\le N$）使得所有小于$j$的$i$ $X_i=Y_i$且$X_j<Y_j$，则称旋律$X<$ 旋律$Y$。 **输入格式** 输入第一行包含四个整数$N(1\le N\le 100\ 000), L,R(1\le L\le R\le 10^9),K(1\le K\le 10^9)$，意义如上所示。 第二行包含$N$个整数$A_i(1\le A_i\le 10^9)$，代表原旋律。 **输出格式** 输出一行$N$个整数（每相邻两个用空格隔开）表示满足所有要求的字典序最小的旋律，若没有旋律满足所有要求，则输出$-1$。请注意，最小的旋律也可能满足所有的要求，即输出可能与原来的旋律相同。 **样例说明** 样例1： 定义$A=\{1,3,5,6,7,8,9,10,3,7,8,9,11,12,12\}$，如下图所示。指向右上方的箭头表示$A_i<A_{i+1}$，指向右侧的箭头表示$A_i=A_{i+1}$，指向右下角的箭头表示$A_i>A_{i+1}$。根据$L=1,R=8,K=6$，我们可以得出符合条件且字典序最小的$B=\{1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,8\}$，如图所示。 

题目描述

Andi is a mathematician, a computer scientist, and a songwriter. After spending so much time writing songs, he finally writes a catchy melody that he thought as his best creation. However, the singer who will sing the song/melody has a unique vocal range, thus, an adjustment may be needed. A melody is defined as a sequence of $ N $ notes which are represented by integers. Let $ A $ be the original melody written by Andi. Andi needs to adjust $ A $ into a new melody $ B $ such that for every $ i $ where $ 1 \le i < N $ : - If $ A_i < A_{i+1} $ , then $ B_i < B_{i+1} $ . - If $ A_i = A_{i+1} $ , then $ B_i = B_{i+1} $ . - If $ A_i > A_{i+1} $ , then $ B_i > B_{i+1} $ . - $ |B_i - B_{i+1}| \le K $ , i.e. the difference between two successive notes is no larger than $ K $ . Moreover, the singer also requires that all notes are within her vocal range, i.e. $ L \le B_i \le R $ for all $ 1 \le i \le N $ .Help Andi to determine whether such $ B $ exists, and find the lexicographically smallest $ B $ if it exists. A melody $ X $ is lexicographically smaller than melody $ Y $ if and only if there exists $ j $ ( $ 1 \le j \le N $ ) such that $ X_i = Y_i $ for all $ i < j $ and $ X_{j} < Y_{j} $ . For example, consider a melody $ A = \{1,3,5,6,7,8,9,10,3,7,8,9,10,11,12,12\} $ as shown in the following figure. The diagonal arrow up in the figure implies that $ A_i < A_{i+1} $ , the straight right arrow implies that $ A_i = A_{i+1} $ , and the diagonal arrow down implies that $ A_i > A_{i+1} $ . Supposed we want to make a new melody with $ L = 1 $ , $ R = 8 $ , and $ K = 6 $ . The new melody $ B = \{1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,8\} $ as shown in the figure satisfies all the requirements, and it is the lexicographically smallest possible.

输入输出格式

输入格式

Input begins with a line containing four integers: $ N $ $ L $ $ R $ $ K $ ( $ 1 \le N \le 100\,000 $ ; $ 1 \le L \le R \le 10^9 $ ; $ 1 \le K \le 10^9 $ ) representing the number of notes in the melody, the vocal range ( $ L $ and $ R $ ), and the maximum difference between two successive notes in the new melody, respectively. The next line contains $ N $ integers: $ A_i $ ( $ 1 \le A_i \le 10^9 $ ) representing the original melody.

输出格式

Output in a line $ N $ integers (each separated by a single space) representing the lexicographically smallest melody satisfying all the requirements, or output -1 if there is no melody satisfying all the requirements. Note that it might be possible that the lexicographically smallest melody which satisfies all the requirements to be the same as the original melody.

输入输出样例

输入样例 #1

16 1 8 6
1 3 5 6 7 8 9 10 3 7 8 9 10 11 12 12

输出样例 #1

1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 8

输入样例 #2

16 1 8 6
1 3 5 6 7 8 9 10 3 7 8 9 10 11 12 13

输出样例 #2

-1

输入样例 #3

16 1 10 10
1 3 5 6 7 8 9 10 3 7 8 9 1 11 12 13

输出样例 #3

1 2 3 4 5 6 7 8 1 2 3 4 1 2 3 4

说明

Explanation for the sample input/output #1 This is the example from the problem description.