시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB32266.667%

문제

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

Доктор планирует купить $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$.

예제 입력 1

5 1 1
1
2
3
4
5

예제 출력 1

12 14 15 15 16

예제 입력 2

6 3 2
2
1
3
2
1
5

예제 출력 2

13 15 15 15 17 17