Распродажа!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
booksale.in
вывод
booksale.out

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

Доктор планирует купить n различных книг. По акции при покупке w + q и более книг w самых дешевых из них достаются бесплатно. Доставка одного заказа стоит e монет. Герой может заказать набор различных книг, которых нет в других заказах. Количество книг в одном заказе неограниченно.

К сожалению, доктор забыл значение q. Помогите великому магу. Для каждого значения q от 1 до n найдите минимальное количество монет, которое необходимо потратить, чтобы купить все n книг.

Входные данные

В первой строке заданы числа n, e и w  — количество книг, цена доставки и количество бесплатных книг (1 ≤ w ≤ n ≤ 3·105; 1 ≤ e ≤ 106).

Далее следует n строк. В каждой записано число t  — цена i-ой книги (1 ≤ t ≤ 106).

Выходные данные

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

Примеры

Входные данные
5 1 1
1
2
3
4
5
Выходные данные
12 14 15 15 16 
Входные данные
6 3 2
2
1
3
2
1
5
Выходные данные
13 15 15 15 17 17