/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
長さ N の数列 A があります。
数列 B は A を無限に繰り返したものです。
厳密には、全ての整数 i について B_i = A_{((i-1)\ {\rm mod}\ N) + 1} と定義します。但し、 p\ {\rm mod}\ q は p を q で割った余りとします。
以下の Q 個の質問に答えてください。そのうち i 個目は次の通りです。
- B の L_i 項目から R_i 項目までの総和を求めよ。
制約
- 入力は全て整数
- 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) です。
この入力には 5 個の質問が含まれ、最初の 2 個は次の通りです。
- 1 個目の質問では、 3 項目から 7 項目までの総和を求めます。この値は 4+1+5+9+2 = 21 です。
- 2 個目の質問では、 6 項目から 10 項目までの総和を求めます。この値は 9+2+6+3+1=21 です。
Problem Statement
You are given a sequence A of length N.
Sequence B is an infinite-time repetition of A.
More precisely, define B_i = A_{((i-1)\ {\rm mod}\ N) + 1} for all integers i, where p\ {\rm mod}\ q denotes the remainder when p is divided by q.
Answer the following Q queries. The i-th query is:
- Find the sum of the L_i-th through R_i-th terms of B.
Constraints
- All input values are integers.
- 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}
Input
The input is given from Standard Input in the following format:
N Q A_1 A_2 \dots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
Output
Print Q lines.
The i-th line should contain the answer to the i-th query.
Sample Input 1
8 5 3 1 4 1 5 9 2 6 3 7 6 10 1 16 4 21 1 1000000000000
Sample Output 1
21 21 62 68 3875000000000
We have B=(3,1,4,1,5,9,2,6,3,1,4,1,5,9,2,6,\dots).
This input contains five queries. The first two are as follows.
- For the 1-st query, find the sum of the 3-rd through 7-th terms: 4+1+5+9+2 = 21.
- For the 2-nd query, find the sum of the 6-th through 10-th terms: 9+2+6+3+1=21.