시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB72191237.500%

문제

세린이는 세상에서 가장 커다란 극장인 세린극장의 오너이다. 세린극장에는 왼쪽부터 순서대로 $1$번부터 $N$번까지의 번호가 붙은 총 $N$ 개의 좌석이 있으며, 그 중 $M$ 개의 좌석인 $P_1, P_2, \cdots, P_M$번 좌석은 온라인상으로 예약이 되어 사람들이 이미 도착해 있다.
세린이는 남은 모든 좌석의 표를 오프라인상으로 팔기로 하여, 현재 $N-M$ 명의 손님이 표를 사기 위해 도착해 있다. 모든 손님은 현재 남아있는 좌석 중 가장 쾌적한 좌석에 앉고 싶어 하며, 좌석의 쾌적함은 자신으로부터 가장 가까운 사람이 멀수록 높다. 구체적으로, 표를 사고 새로 들어가는 $i$ 번째 사람이 가장 쾌적하다고 느끼는 자리는 다음과 같다:

  • 자신이 앉았을 때 가장 가까운 사람과의 거리가 가장 먼 자리
  • 그런 곳이 여러 개라면, 다음 사람이 들어와서 앉았을 때  자신과 가장 가까운 사람과의 거리가 가장 먼 자리
  • 그런 곳이 여러 개라면, 그다음 사람이 들어와서 앉았을 때 자신과 가장 가까운 사람과의 거리가 가장 먼 자리

$\vdots$

  • 그런 곳이 여러 개라면, $(N-M-i)$ 번째 다음으로 들어온 사람이 앉았을 때 자신과 가장 가까운 사람과의 거리가 가장 먼 자리
  • 그런 곳이 여러 개라면, 번호가 가장 작은 자리

오프라인 상으로 표를 사러 온 첫 $K$ 명의 VIP 손님에게는 세린이가 직접 손님들을 안내하고 싶었다. 하지만, 세린극장에는 좌석이 너무 많아 세린이는 손님을 어느 좌석으로 안내해야 할지 알 수 없다. 여러분이 세린이를 도와 손님들을 가장 쾌적한 좌석으로 안내해주자.

입력

첫 번째 줄에는 $N, M, K$가 공백으로 구분되어 주어진다.

두 번째 줄에는 $P_1, P_2, \cdots, P_M$이 공백으로 구분되어 주어진다.

출력

$K$ 개의 줄을 출력한다. 이 중 $i$ 번째 줄에는 $i$ 번째로 들어가는 사람에게 안내해 주어야 하는 자리의 번호를 출력한다.

제한

  • $1 \le N \le 10^{18}$
  • $1 \le M \le 1\,000\,000$
  • $1 \le K \le 1\,000\,000$
  • $K \le N-M$
  • $1 \le P_i \le N$ $(1 \le i \le M)$
  • $P_i \ne P_j$ $(1 \le i < j \le M)$
  • 입력으로 주어지는 모든 수는 정수다.

예제 입력 1

5 1 4
3

예제 출력 1

5
1
2
4

예제 입력 2

10 1 9
6

예제 출력 2

1
10
8
4
2
3
5
7
9

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2021! G번