페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8017
서브태스크

가로등 2초 1024MB

문제

수직선 도로 위에 N개의 가로등이 켜져 있다. 각 가로등의 위치는 왼쪽부터 차례대로 A_1 \lt \cdots \lt A_N 로 나타낼 수 있다.

위치 x의 어두운 정도를, 그 위치로부터 가장 가까운 가로등까지의 거리로 정의하다. 이는 N개의 수 |A_1 - x|, \cdots,|A_N-x| 중에서 가장 작은 값과 같다. 여기서 |\cdot|는 절댓값 기호로, y\ge0이면 ,|y|:=y, y \lt 0이면 |y|:=-y이다.

예를 들어, N=3개의 가로등이 차례대로 A_1 = 1, A_2 = 4, A_3 = 8에 위치한다면, 0부터 10까지 각 정수 위치의 어두운 정도는 다음과 같다.

위치

0

1

2

3

4

5

6

7

8

9

10

어두운 정도

1

0

1

1

0

1

2

1

0

1

2

가로등이 있는가?

O

O

O

x=0부터, x=L까지 L+1개의 정수 위치의 어두운 정도를 모두 계산했을 때, 가장 작은 값부터 K번째로 작은 값까지 차례대로 출력하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다. 

  • 1 ≤ L ≤ 1,000,000,000,000,000,000  

  • 1 ≤ N ≤ 300,000  

  • 1 ≤ K ≤ 500,000  

  • K ≤ L + 1  

  • 0 ≤ A_1 < A_2 < \cdots < A_N ≤ L 


입력

첫 줄에 세 정수 L, N, K가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 N 개의 정수 A_1, \cdots , A_N이 공백으로 구분되어 차례대로 주어진다.


출력

첫 줄부터 K 개의 줄에 걸쳐 답을 출력한다. 이 중 i 번째 줄에는 i 번째로 작은 어두운 정도의 값을 출력한다.


부분문제

번호 점수 조건
#110점

N = 1

#220점

N \le 2,500, L \le 2,500

#315점

2 \le N. N-1은 L을 나눈다. A_i = \frac{L}{N - 1} \times (i - 1) 

#420점

L \le 5,000,000

#535점

추가 제약 조건 없음.


예제1

입력
1034
148
출력
0
0
0
1

예제2

입력
455
01234
출력
0
0
0
0
0

예제3

입력
714
3
출력
0
1
1
2

예제4

입력
9410
0369
출력
0
0
0
0
1
1
1
1
1
1

출처

2024 KOI 2차 초2/중1/고1

역링크