P10097: 突袭

---

【题目描述】

【题目描述】
如你所知，地球上最聪明的生物当然是奶牛。这个结论在很久以前就被火星上的外星人，以及其他一些来自外太空的智慧文明所得出。
有时牛会聚集成牛群。这似乎是季节性的。但在这个时候，奶牛变得被动，对外部刺激的反应很差。科瓦万农场是火星科学飞碟的完美目标，是时候进行大规模绑架了，或者像火星人所说的那样，进行突袭了。简单地说，奶牛场是一排奶牛。
如果我们用从1到n的正整数对科瓦万农场中的所有奶牛进行编号，那么我们就可以形式化流行的绑架模型，称为（a，b）-Covan突袭:首先他们偷了一头编号为a的奶牛，然后是编号为a+b的奶牛，然后是编号为a+2b的奶牛，以此类推，直到被绑架的奶牛的数量超过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说明符在c++中读写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

【提示】

Time to Raid Cowavans
As you know, the most intelligent beings on the Earth are, of course, cows.  This conclusion was reached long ago by the Martian aliens, as well as a number of other intelligent civilizations from outer space.
Sometimes cows gather into cowavans.  This seems to be seasonal.  But at this time the cows become passive and react poorly to external stimuli.  A cowavan is a perfect target for the Martian scientific saucer, it's time for large-scale abductions, or, as the Martians say, raids.  Simply put, a cowavan is a set of cows in a row.

If we number all cows in the cowavan with positive integers from 1 to n, then we can formalize the popular model of abduction, known as the (a,b)-Cowavan Raid: first they steal a cow number a, then number a+b, then − number a+2·b, and so on, until the number of an abducted cow exceeds n. During one raid the cows are not renumbered.

The aliens would be happy to place all the cows on board of their hospitable ship, but unfortunately, the amount of cargo space is very, very limited.  The researchers, knowing the mass of each cow in the cowavan, made p scenarios of the (a,b)-raid.  Now they want to identify the following thing for each scenario individually: what total mass of pure beef will get on board of the ship.  All the scenarios are independent, in the process of performing the calculations the cows are not being stolen.


Input
The first line contains the only positive integer n (1≤n≤3·105) − the number of cows in the cowavan.

The second number contains n positive integer wi, separated by spaces, where the i-th number describes the mass of the i-th cow in the cowavan (1≤wi≤109).

The third line contains the only positive integer p − the number of scenarios of (a,b)-raids (1≤p≤3·105).

Each following line contains integer parameters a and b of the corresponding scenario (1≤a,b≤n).

Output
Print for each scenario of the (a,b)-raid the total mass of cows, that can be stolen using only this scenario.

Please, do not use the %lld specificator to read or write 64-bit integers in C++.  It is recommended to use the cin, cout streams of the %I64d specificator.

Examples
Input
3
1 2 3
2
1 1
1 2
Output
6
4
Input
4
2 3 5 7
3
1 3
2 3
2 2
Output
9
3
10

题目类型~

 

咻咻~

提交答案 状态 返回