题目描述

在一片广阔的麦田中，农夫种植了 $n$ 株麦穗，从左到右编号为 $1$ 到 $n$。每株麦穗的产量已知。农夫想采用一种特殊的收割方式：每次选定一个起始编号 $a$ 和一个间隔 $b$，然后收割编号为 $a$,$a+b$,$a+2b$,$…$的麦穗，直到编号超过 $n$ 为止。不同的收割方案互不影响，即每次都是独立地从完整的麦田中选择。 现在农夫准备了 $p$ 种不同的收割方案，请你帮忙计算每种方案下能收获的总产量。

输入格式

第一行一个正整数 $n$，表示麦穗总数。 第二行 $n$ 个正整数 $w_i$，表示第 $i$ 株麦穗的产量。 第三行一个正整数 $p$，表示收割方案的数量。 接下来 $p$ 行，每行两个整数 $a$ 和 $b$，表示一种收割方案的起始编号和间隔。

输出格式

对于每种收割方案，输出一行一个整数，表示该方案能收获的总产量。

样例

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

数据范围

对于$20$%的数据

• $1<=n<=1000$

对于$100$%的数据

• $1<=n,p<=3*10^5$
• $1<=a,b<=n$
• $1<=w_i<=10^9$