수직선 도로 위에 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

#8017 upload 1203 done 239 how_to_reg 189 call_split Subtask

가로등 timer 2s memory 1024MB

#8017
Subtask

가로등 2s 1024MB