Andi 是一位数学家、计算机科学家和歌曲作者。在花了这么多时间写歌之后,他终于写出了一首朗朗上口的旋律,他认为这是他最好的创作。然而,演唱该歌曲/旋律的歌手具有独特的音域,因此可能需要进行调整。
旋律被定义为由整数表示的 $$$N$$$ 音符序列。令 $$$A$$$ 为 Andi 创作的原始旋律。 Andi 需要将 $$$A$$$ 调整为新的旋律 $$$B$$$,这样对于每个 $$$i$$$ 其中 $$$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$$$。
帮助Andi判断这样的$$$B$$$是否存在,如果存在则找到字典序最小的$$$B$$$。旋律 $$$X$$$ 按字典顺序小于旋律 $$$Y$$$ 当且仅当存在 $$$j$$$ ($$$1 \le j \le N$$$) 使得 $$$X_i = Y_i$$$ 对于所有 $$$i < j$$$ 和 $$$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\}$$$ 满足所有要求,并且是字典顺序上最小的。
输入
输入以包含四个整数的行开头: $$$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
输入 #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
注意
示例输入/输出 #1 的说明
这是问题描述中的示例。