문제
여러분은 N명의 게임 캐릭터를 육성하려고 한다. i(1 ≤ i ≤ N)번째 캐릭터의 현재 레벨은 Li 이다.
캐릭터의 레벨을 올리기 위해 아래와 같은 트레이닝을 총 M번 진행할 것이다.
• 레벨이 낮은 순서대로 K명의 캐릭터를 선택한다. 레벨이 같은 캐릭터가 여러 명일 경우 그중 아무 캐릭터나 선택한다.
• 선택된 캐릭터들의 레벨을 각각 1만큼 올린다.
예를 들어, M = 4, K = 3이고 N = 5명의 캐릭터의 레벨이 각각 5, 1, 7, 5, 4라고 하자.
트레이닝을 한 번 진행하면 2, 4, 5번째 캐릭터의 레벨이 오르고, 이때 캐릭터의 레벨은 각각 5, 2, 7, 6, 5가 된다.
위의 예시에서 각 트레이닝을 진행한 이후 캐릭터의 레벨은 다음과 같다.
M 번의 트레이닝이 모두 끝난 이후 N 명의 캐릭터의 레벨을 오름차순으로 출력하는 프로그램을 작성하시오.
[제약 조건]
• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 109
• 1 ≤ K ≤ N
• 1 ≤ Li ≤ 109 (1 ≤ i ≤ N)
입력
첫 번째 줄에 캐릭터의 수를 나타내는 정수 N이 주어진다.
두 번째 줄에 각 캐릭터의 레벨을 나타내는 정수 L1, ···, Ln이 공백으로 구분되어 주어진다.
세 번째 줄에 정수 M, K가 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 모든 트레이닝이 끝난 이후 캐릭터들의 레벨을 오름차순으로 정렬하여 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 4점 | |
| #2 | 10점 | |
| #3 | 32점 | |
| #4 | 54점 | 추가 제약 조건 없음 |
예제1
입력
5
51754
43
출력
57778
예제2
입력
4
7429
101
출력
7889
출처
KOI 2차 2022 중4/고3