CF1252E.Songwriter

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 \lt N$:

• If $A_i \lt A_{i+1}$, then $B_i \lt B_{i+1}$.
• If $A_i = A_{i+1}$, then $B_i = B_{i+1}$.
• If $A_i \gt A_{i+1}$, then $B_i \gt 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 \lt j$ and $X_{j} \lt 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 \lt A_{i+1}$, the straight right arrow implies that $A_i = A_{i+1}$, and the diagonal arrow down implies that $A_i \gt 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.

安迪是一位数学家、计算机科学家，也是一位词曲作者。在花费大量时间创作歌曲后，他终于写出了一段自己认为最出色的动人旋律。然而，即将演唱这首歌曲/旋律的歌手拥有独特的音域，因此可能需要对旋律进行调整。

一段旋律被定义为由 $N$ 个音符组成的序列，每个音符用一个整数表示。设 $A$ 为安迪最初创作的旋律。安迪需要将 $A$ 调整为一个新的旋律 $B$，使得对每个满足 $1 \le i < 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$。

此外，歌手还要求所有音符均需落在她的音域范围内，即对所有 $1 \le i \le N$，均有 $L \le B_i \le R$。

请帮助安迪判断是否存在满足上述条件的旋律 $B$；若存在，请找出字典序最小的 $B$。旋律 $X$ 字典序小于旋律 $Y$ 当且仅当存在某个下标 $j$（$1 \le j \le N$），使得对所有 $i < j$ 都有 $X_i = Y_i$，且 $X_j < Y_j$。

例如，考虑旋律 $A = \{1,3,5,6,7,8,9,10,3,7,8,9,10,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\}$ 满足全部要求，且是字典序最小的可行解。

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.

输入的第一行包含四个整数：$N$ $L$ $R$ $K$（$1 \le N \le 100\,000$；$1 \le L \le R \le 10^9$；$1 \le K \le 10^9$），分别表示旋律中的音符数量、人声音域（$L$ 和 $R$）以及新旋律中相邻两个音符之间的最大差值。下一行包含 $N$ 个整数：$A_i$（$1 \le A_i \le 10^9$），表示原始旋律。

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.

在一行中输出 $N$ 个整数（每个整数之间用一个空格分隔），表示满足所有要求的字典序最小的旋律；若不存在满足所有要求的旋律，则输出 -1。注意：满足所有要求的字典序最小的旋律有可能与原始旋律完全相同。

Explanation for the sample input/output #1

This is the example from the problem description.

样例输入/输出 #1 的说明

这是题目描述中的示例。