A34872.热心公主分担宝物

时间限制：2S
空间限制：1024MB

算法一姐超楠认为上学的题目太简单所以现在她又来搞事情了。
现在兴科手上有 $n$ 件宝物编号为 $1 \sim n$ ，每一件宝物都有属于自己的珍稀度，超楠看兴科手上的宝物太多了决定做好事帮他分担一部分宝物，但是这些宝物都是兴科好不容易弄到的,所以兴科决定让超楠选择花费一定的代价在前 $x$ 件宝物中选择连续的最多 $y$ 件宝物带走，并且带走的这些宝物的起始编号对 $y$ 求余必须为 1 ，即 $i \% y = 1$，特别的对于 $y = 1$ 的时候没有起始位置的限制。超楠的小脑袋瓜不够用她只能解决掉代价的那一部分问题，她找到了你来帮助她完成剩余部分：超楠会对你进行 $m$ 次询问，每一次会告诉你 $x$ 与 $y$ 的值请你回答她在此条件下超楠能拿到宝贝珍稀度和的最大值。

第一行输入一个整数 $n$ 代表宝物数，第二行输入 $n$ 个整数 $a_i$ 代表第 $i$ 个宝物的珍稀度，第三行给出一个整数 $m$ 代表超楠的询问次数，紧随其后 $m$ 行每一行输入两个整数 $x,y$ 如题意。对于所有数据($1 \le n \le 2 \times 10^5;1 \le m \le 5 \times 10^5;1 \le x,y \le n;1 \le a_i \le 10^9$ );

输出 $m$ 行，对于每一次询问给出你的回答。