← 返回题目列表

Codeforces · 1252/E

E. 歌曲作者

中文机器翻译题面 查看原题

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 的说明

这是问题描述中的示例。