问题陈述
给你一个序列 A 长度 N.
序列 B 是无限次重复 A.
更准确地说,定义 B_i = A_{((i-1)\ {\rm mod}\ N) + 1} 对于所有整数 i,其中 p\ {\rm mod}\ q 表示当 p 除以 q.
回答以下问题 Q 查询。 i第一个查询是:
- 求总和 L_i-th 通过 R_i第项 B.
约束
- 所有输入值均为整数。
- 1 \le N \le 2 \times 10^5
- 1 \le Q \le 2 \times 10^5
- 0 \le A_i \le 10^6
- 1 \le L_i \le R_i \le 10^{12}
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 \dots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
输出
打印 Q 行。
的 i- 第行应包含以下问题的答案 i-第一个查询。
示例输入 1
8 5 3 1 4 1 5 9 2 6 3 7 6 10 1 16 4 21 1 1000000000000
示例输出 1
21 21 62 68 3875000000000
我们有 B=(3,1,4,1,5,9,2,6,3,1,4,1,5,9,2,6,\dots).
此输入包含五个查询。前两个如下。
- 对于 1-st查询,求总和 3-rd 通过 7第项: 4+1+5+9+2 = 21.
- 对于 2-nd查询,求总和 6-th 通过 10第项: 9+2+6+3+1=21.