Sale!

Doctor Strange likes to read and study new spells. His favorite bookstore, 'Dormammu', is having a sale! But the doctor is stuck in a time loop and has no time, so he decided to order all the books online for delivery.

The doctor plans to buy $n$ distinct books. During the sale, when buying $w + q$ or more books, the $w$ cheapest of them are free. Delivery of one order costs $e$ coins. The doctor can order a set of distinct books that are not in any other order. There is no limit on the number of books in one order.

The doctor forgot the value of $q$. For each $q$ from $1$ to $n$, find the minimum number of coins needed to buy all $n$ books.

The first line contains three integers $n$, $e$, and $w$: the number of books, the delivery cost, and the number of free books ($1 \le w \le n \le 3 \cdot 10^5$; $1 \le e \le 10^6$).

Each of the next $n$ lines contains $t$, the price of the $i$-th book ($1 \le t \le 10^6$).

Print $n$ numbers: the minimum number of coins needed to buy all books for each $q$ from $1$ to $n$.