세일!

닥터 스트레인지는 마법 주문이 담긴 책을 읽고 배우는 것을 좋아한다. 그가 즐겨 찾는 서점 「도르마무」에서 세일을 한다. 하지만 닥터는 시간 고리에 갇혀 시간이 부족해서, 필요한 책을 모두 인터넷으로 주문해 배송받기로 했다.

닥터는 서로 다른 책 $n$권을 사려고 한다. 세일 조건은 다음과 같다. 책을 $w + q$권 이상 구매하면, 그중 가장 싼 $w$권을 무료로 준다. 주문 한 건의 배송비는 $e$코인이다. 주문에는 다른 주문에 들어 있지 않은 책들만 담을 수 있다. 한 주문에 담을 수 있는 책 수에는 제한이 없다.

닥터는 $q$의 값을 잊어버렸다. $q$가 $1$부터 $n$까지 각각일 때, 책 $n$권을 모두 사는 데 필요한 최소 코인 수를 구하라.

첫 줄에 책의 수 $n$, 배송비 $e$, 무료 책의 수 $w$가 주어진다 ($1 \le w \le n \le 3 \cdot 10^5$, $1 \le e \le 10^6$).

이어서 $n$개의 줄이 주어지며, 각 줄에는 $i$번째 책의 가격 $t$가 적혀 있다 ($1 \le t \le 10^6$).

$q$가 $1$부터 $n$까지일 때의 답을 $n$개의 수로 출력하라.