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