만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

대안적 사실

시간 제한1.5초메모리 제한256 MB

요약
배열 A를 재배열한 B를 만들어, 앞 L개 위치의 값이 원래 값과 K 이내로 차이 나도록 하면서 사전순으로 가장 큰 B를 구합니다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 힙
정답자
아직 제출이 없습니다

문제

서기 3020년, 미국 제 237대 대통령의 취임식이 열렸다. 아니, 정확히 말하자면 대통령들의 취임식이라고 해야 할 것이다. 미국은 2884년 대선부터 N두제를 도입하여 N명의 대통령을 선출하기 때문이다.

서현이는 유명 언론사의 정치부 기자로, 모든 취임식에 참석했다. 서현이는 ii번째 대통령의 취임식에 참석한 사람이 AiA_i명이라는 사실을 알아냈다.

이제 서현이는 이를 바탕으로 기사를 쓰려고 한다. 다만 기사의 내용이 꼭 사실일 필요는 없고, 대안적 사실이면 충분하다고 생각한다. 길이가 NN인 수열 BB가 수열 AA의 대안적 사실이려면 다음 두 조건을 만족해야 한다.

  • BB는 AA를 임의의 순서로 섞은 수열이다. 즉, AA와 BB를 각각 정렬했을 때 결과가 같다.
  • 모든 정수 1≤i≤L1 \le i \le L에 대해 ∣Ai−Bi∣≤K|A_i - B_i| \le K이다. 이때 KK와 LL은 서현이가 생각하고 있는 음이 아닌 정수이다.

서현이는 기사에 적을 대안적 사실이 가장 위대하기를 바란다. 수열 BB가 다른 수열 CC보다 위대하다는 것은 두 수열이 처음으로 달라지는 ii번째 항에서 Bi>CiB_i > C_i임을 뜻한다. 즉, BB가 CC보다 사전순으로 뒤에 온다는 뜻이다.

서현이를 위해 가장 위대한 대안적 사실을 찾아 주자.

입력

첫째 줄에 양의 정수 NN과 음이 아닌 정수 KK, LL이 주어진다. (1≤N≤200,0001 \le N \le 200{,}000, 0≤K≤1090 \le K \le 10^9, 0≤L≤N0 \le L \le N)

둘째 줄에 길이 NN인 수열 AA가 공백으로 구분되어 주어진다. (1≤Ai≤1091 \le A_i \le 10^9)

출력

첫째 줄에 수열 AA의 가장 위대한 대안적 사실을 공백으로 구분하여 출력한다.

예제4

  1. 예제 1

    입력
    5 3 5
    7 6 1 9 4
    
    예상 출력
    9 7 4 6 1
    
  2. 예제 2

    입력
    5 2 5
    7 6 1 9 4
    
    예상 출력
    9 6 1 7 4
    
  3. 예제 3

    입력
    5 2 3
    7 6 1 9 4
    
    예상 출력
    9 7 1 6 4
    
  4. 예제 4

    입력
    5 2 0
    7 6 1 9 4
    
    예상 출력
    9 7 6 4 1