← 返回题目列表

Codeforces · 103/D

D. 是时候袭击 Cowavans 了

中文机器翻译题面 查看原题

如您所知,地球上最聪明的生物当然是牛。这个结论是火星外星人以及其他一些来自外太空的智慧文明很早就得出的。

有时,奶牛会聚集成牛群。这似乎是季节性的。但此时奶牛变得被动,对外界刺激反应不佳。牛仔队是火星科学飞碟的完美目标,现在是大规模绑架的时候了,或者用火星人的话来说,是袭击。简单地说,牛队就是一群排成一排的牛。

如果我们用从 1 到 n 的正整数对牛群中的所有奶牛进行编号,那么我们就可以将流行的绑架模型形式化,称为 (a, b)-Cowavan Raid:首先他们偷走编号为 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)-raid的场景数量(1≤p≤3·105)。

接下来的每一行包含相应场景的整数参数 a 和 b (1 ≤ a, b ≤ n)。

输出

打印 (a, b)-raid 的每个场景中仅使用此场景即可窃取的奶牛的总质量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。建议使用 %I64d 说明符的 cin、cout 流。

示例

输入 #1

3
1 2 3
2
1 1
1 2

输出 #1

6
4

输入 #2

4
2 3 5 7
3
1 3
2 3
2 2

输出 #2

9
3
10