CF1252E Songwriter

安迪是数学家，计算机科学家和作曲家。潜心创作很长时间后，他终于写出了一首他认为是他最好的作品。但是，每位歌手有一个独特的音域，因此可能需要调整。 旋律被定义为$N$个音符的序列（保证$N$为整数）。$A$是安迪创作的原旋律。现在需要把$A$调整成一个新的旋律B，这样对于每个小于$N$的$i$： - 若$A_iB_{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

输入第一行包含四个整数$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_iA_{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\}$，如图所示。