Andi 是一位数学家、计算机科学家，也是一位作曲家。在花费了大量时间创作歌曲后，他终于写出了一段他认为是他最好的作品的动听旋律。然而，演唱这首歌/旋律的歌手有着独特的音域，因此可能需要进行调整。
旋律定义为由整数表示的 $N$ 个音符组成的序列。设 $A$ 为 Andi 创作的原始旋律。Andi 需要将 $A$ 调整为一段新旋律 $B$，使得对于每个 $1 \le i < N$：
- 如果 $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$。
请帮助 Andi 确定是否存在这样的 $B$，如果存在，请找出字典序最小的 $B$。当且仅当存在某个 $j$ ($1 \le j \le N$) 使得对于所有 $i < j$ 都有 $X_i = Y_i$ 且 $X_j < Y_j$ 时，称旋律 $X$ 的字典序小于旋律 $Y$。
例如，考虑旋律 $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\}$ 满足所有要求，并且是字典序最小的可能旋律。
输入格式
输入的第一行包含四个整数：$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$)，表示原始旋律。
输出格式
输出一行 $N$ 个整数（每个整数之间用单个空格分隔），表示满足所有要求的字典序最小的旋律；如果不存在满足所有要求的旋律，则输出 $-1$。注意，满足所有要求的字典序最小的旋律可能与原始旋律相同。
样例
样例输入 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
说明 1
这是题目描述中的示例。
样例输入 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