Распродажа!

Доктор Стрэндж любит читать и изучать новые заклинания. В его любимом книжном магазине <<У Дормамму>> акция! Но доктор попал во временную петлю, и у него не хватает времени, поэтому все книги он решил заказать с доставкой через интернет.

Доктор планирует купить $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$ строк. В каждой записано число $t$ --- цена i-ой книги ($1 \le t \le 10^6$).

Выведите $n$ чисел --- минимальное количество монет, необходимое для покупки всех книг, при значении $q$ от $1$ до $n$.