시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 13 6 5 41.667%

문제

서기 3020년, 미국 제 237대 대통령의 취임식이 열렸다. 아니, 정확히 말하자면 대통령들의 취임식이라고 해야 할 것이다. 미국은 2884년 대선부터 N두제를 도입하여 N명의 대통령이 선출되니까 말이다. 서현이는 유명 언론사의 정치부 기자로써, 모든 취임식에 참석하여 i번째 대통령의 취임식에 참석한 사람은 Ai명이라는 사실을 알아냈다.

이제 서현이는 이를 바탕으로 기사를 쓰려고 한다. 하지만 서현이는 기사에 적힌 내용이 꼭 사실일 필요까지는 없고, 대안적 사실인 정도면 충분하다고 생각한다.

이 때 길이가 N인 수열 B가 A의 대안적 사실이라는 것은 다음을 의미한다.

  • B는 A를 임의의 순서로 섞은 수열이다. 즉, A와 B를 각각 정렬했을 때의 결과가 같다.
  • 임의의 정수 1 ≤ i ≤ L에 대해 |Ai - Bi| ≤ K이다. 이 때 K와 L은 서현이가 생각하고 있는 어떤 음이 아닌 정수이다.

또한 서현이는 기사에 적을 대안적 사실이 가장 위대하기를 바라고 있다. 어떤 수열 B가 다른 수열 C보다 위대하다는 것은 두 수열이 i번째 항에서 처음으로 달라질 때 Bi > Ci임을 의미한다. 다시 말해, B가 C보다 사전순으로 뒤에 옴을 의미한다.

기사에 적을 내용을 고민하는 서현이를 위해 가장 위대한 대안적 사실을 찾아주자!

입력

첫째 줄에 양의 정수 N과 음이 아닌 정수 K, L이 주어진다. (1 ≤ N ≤ 200,000, 0 ≤ K ≤ 109, 0 ≤ L ≤ N)

둘째 줄에 길이 N의 수열 A가 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ 109)

출력

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

예제 입력 1

5 3 5
7 6 1 9 4

예제 출력 1

9 7 4 6 1

예제 입력 2

5 2 5
7 6 1 9 4

예제 출력 2

9 6 1 7 4

예제 입력 3

5 2 3
7 6 1 9 4

예제 출력 3

9 7 1 6 4

예제 입력 4

5 2 0
7 6 1 9 4

예제 출력 4

9 7 6 4 1

출처

High School > 서울과학고등학교 > 2020 SciOI #1 G번