D. Время грабить корованы
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
70 megabytes
ввод
stdin
вывод
stdout
Я джва года хочу такую задачу.
Alex_KPR

Как известно, самые умные существа на планете Земля — это, конечно, коровы. К этому выводу давно пришли марсианские инопланетяне, а также целый ряд других разумных цивилизаций из дальнего космоса.

Иногда коровы собираются в корованы. Это, кажется, у них сезонное. Но именно в это время коровы становятся пассивными и слабо реагируют на внешние раздражители. Корован — идеальная мишень для марсианской исследовательской тарелки, самое время для крупномасштабных похищений, или, как говорят марсиане, ограблений. Говоря простым языком, корован — это множество коров, расположенных в ряд.

Если пронумеровать всех коров в короване натуральными числами от 1 до n, то можно формализовать популярную модель похищения, известную как (a, b)-ограбление корована: сперва похищается корова с номером a, затем — с номером a + b, затем — с номером a + 2·b, и так далее, пока номер похищаемой коровы не превысит n. В процессе одного ограбления коровы не перенумеровываются.

Инопланетяне с радостью бы расположили всех коров на борту своего гостеприимного судна, но, к сожалению, размер грузового отсека весьма и весьма ограничен. Исследователи, зная массу каждой коровы в короване, составили p сценариев (a, b)-ограбления. Теперь они хотят определить для каждого сценария в отдельности какая суммарная масса чистой говядины попадет на борт корабля. Все сценарии независимы, в процессе выполнения расчетов похищение коров не осуществляется.

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

В первой строке дано единственное натуральное число n — количество коров в короване (1 ≤ n ≤ 3·105).

Во второй строке содержится n натуральных чисел wi, разделенных пробелами, где i-ое число определяет массу i-ой коровы в короване (1 ≤ wi ≤ 109).

В третьей строке дано единственное натуральное число p — количество сценариев (a, b)-ограблений (1 ≤ p ≤ 3·105).

Каждая последующая строка содержит параметры a и b очередного сценария (1 ≤ a, b ≤ n).

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

На каждый сценарий (a, b)-ограбления выведите суммарную массу коров, которые могут быть похищены в результате ограбления по этому сценарию.

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

Примеры
Входные данные
3
1 2 3
2
1 1
1 2
Выходные данные
6
4
Входные данные
4
2 3 5 7
3
1 3
2 3
2 2
Выходные данные
9
3
10