가방

상훈이는 KOI 도시에서 상점을 운영하고 있는 시민이다. 상훈이의 상점은 $N$개의 물건을 가지고 있으며, 이 중 $i$번째 물건의 무게는 $A_i$이다. 상훈이는 도둑 김기범이 본인의 상점을 노리고 있다는 첩보를 들었고, 이에 대비해 피해를 최소화하려고 한다.

도둑 김기범은 가게에서 $K$개의 물건을 훔쳐갈 것인데, 물건이 무거울 경우 훔쳐가기 어렵고 경찰한테 걸릴 가능성이 높다. 고로, 도둑 김기범은 훔쳐가는 물건의 무게의 합을 최소화한다. 만약 가게에 있는 물건의 개수가 $K$개 미만일 경우, 도둑 김기범은 가게에 있는 모든 물건을 훔쳐간다.

상훈이는 도둑 김기범이 가게를 도착하기 전에, 가방에 상점의 물건들을 몇 개 담아서 들고 갈 것이다. 이후, 도둑 김기범은 상훈이가 들고 가지 않은 물건들에 대해 위에 설명한 방식으로 범죄를 저지른다. 상훈이는 가방에 물건을 적당히 담아서 도둑 김기범이 훔쳐가는 물건의 무게 합을 최대화하려고 한다.

상훈이의 가방이 감당할 수 있는 무게는 한정되어 있다. 입력으로 최댓값 $C$가 주어졌을 때, 모든 $x = 1, 2, \dots , C$에 대해 다음 질문에 답하라:

• 상훈이가 가방에 담을 수 있는 물건들의 무게 합이 $x$이하여야 한다는 조건하에, 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값은 얼마인가?

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

두 번째 줄에 $N$개의 정수 $A_1 , A_2 , \dots , A_N$이 공백으로 구분되어 주어진다.

$C$개의 줄을 출력한다. $i$번째 줄에는, $x = i$일 때 도둑 김기범이 훔쳐가는 물건들의 무게 합의 최댓값을 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 ≤ K ≤ N ≤ 5\, 000$
• $1 ≤ C ≤ 1\, 000\, 000$
• 모든 $i$ ($1 ≤ i ≤ N$)에 대해 $1 ≤ A_i ≤ 1\, 000\, 000$