작곡가

Andi는 수학자이자 컴퓨터 과학자이자 작곡가다. 오랜 시간 곡을 쓰던 끝에, 그는 마침내 자신의 최고 작품이라고 생각하는 귀에 잘 붙는 멜로디를 하나 썼다. 하지만 이 노래를 부를 가수는 독특한 음역을 가졌기 때문에 조정이 필요할 수도 있다.

멜로디는 정수로 표현되는 N개의 음의 수열로 정의한다. Andi가 쓴 원래 멜로디를 A라 하자. Andi는 A를 새 멜로디 B로 조정해야 하며, 1 ≤ i < N인 모든 i에 대해 다음을 만족해야 한다.

• Ai < Ai+1이면 Bi < Bi+1이다.
• Ai = Ai+1이면 Bi = Bi+1이다.
• Ai > Ai+1이면 Bi > Bi+1이다.
• |Bi − Bi+1| ≤ K, 즉 연속한 두 음의 차이는 K 이하다.

또한 가수는 모든 음이 자신의 음역 안에 있어야 한다는 조건도 요구한다. 즉, 모든 1 ≤ i ≤ N에 대해 L ≤ Bi ≤ R이다.

Andi를 도와 이런 B가 존재하는지 판별하고, 존재한다면 사전순으로 가장 작은 B를 찾아라. 멜로디 X가 멜로디 Y보다 사전순으로 작다는 것은, 모든 i < j에 대해 Xi = Yi이고 Xj < Yj인 j (1 ≤ j ≤ N)가 존재한다는 뜻이다.

예를 들어 다음 그림에 나타난 멜로디 A = {1, 3, 5, 6, 7, 8, 9, 10, 3, 7, 8, 9, 10, 11, 12, 12}를 보자. 그림에서 위로 향한 대각선 화살표는 Ai < Ai+1, 오른쪽으로 향한 직선 화살표는 Ai = Ai+1, 아래로 향한 대각선 화살표는 Ai > Ai+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 ≤ N ≤ 100 000; 1 ≤ L ≤ R ≤ 109; 1 ≤ K ≤ 109)를 포함한 한 줄로 시작한다. 이는 각각 멜로디의 음 개수, 음역 (L과 R), 새 멜로디에서 연속한 두 음의 최대 차이를 나타낸다. 다음 줄에는 원래 멜로디를 나타내는 N개의 정수 Ai (1 ≤ Ai ≤ 109)가 주어진다.

모든 조건을 만족하는 사전순으로 가장 작은 멜로디를 나타내는 N개의 정수를 한 줄에 하나씩 공백으로 구분해 출력하거나, 모든 조건을 만족하는 멜로디가 없으면 -1을 출력한다. 모든 조건을 만족하는 사전순으로 가장 작은 멜로디가 원래 멜로디와 같을 수도 있다.