B. Непослушные кучки камней
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На столе перед Вами лежат n кучек камней размера a1, a2, ..., an.

За одно действие можно взять одну кучку и присоединить ее к другой. Причем при присоединении кучки i к кучке j размер кучки j увеличивается на текущий размер кучки i, а кучка i перестает существовать. Стоимость операции присоединения равна размеру присоединяемой кучки.

Ваша задача — определить минимальную стоимость, за которую можно собрать все камни в одну кучу.

Чтобы жизнь не казалась Вам слишком сладкой, кучки камней сговорились и решили, что каждая позволит совершить операцию присоединения к себе не более k раз (после чего только ее саму можно будет присоединить к другой кучке).

Более того, чтобы совсем сбить Вас с толку, кучки камней сообщили Вам q вариантов (необязательно различных) того, чему может быть равно k.

Ваша задача — найти минимальную стоимость для каждого из q вариантов.

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

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество кучек камней. Во второй строке записаны n целых чисел через пробел: a1, a2, ..., an (1 ≤ ai ≤ 109) — первоначальные размеры кучек камней.

В третьей строке записано целое число q (1 ≤ q ≤ 105) — количество запросов. В последней строке — q целых чисел через пробел k1, k2, ..., kq (1 ≤ ki ≤ 105) — значения числа k для разных запросов. Обратите внимание, числа ki могут повторяться.

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

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

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
5
2 3 4 1 1
2
2 3
Выходные данные
9 8
Примечание

В первом случае одним из способов достижения оптимального ответа является следующий: поочередно добавить 4-ю и 5-ю кучки ко 2-й; затем добавить 1-ю кучку к 3-й; добавить 2-ю кучку к 3-й. Первые две операции стоят по 1; третья — 2, четвертая — 5 (размер 2-й кучки после первых двух операций уже не 3, а 5).

Во втором случае можно добавить 2-ю кучку к 3-й (стоимость операции — 3); затем 1-ю к 3-й (стоимость — 2); далее 5-ю к 4-й (стоимость — 1); и, наконец, 4-ю к 3-й (стоимость — 2).