Description

小辉制作了一个显示器，该显示器显示的数值 a1、a2、a3...an 是一开始就植 入的,并会按照次序依次循环显示，每秒变化 1 次。也就是说，该显示器显示的 数值是按照以下规律变化的：
a1—>a2—>a3...—>an—>a1—>a2...—>an—>a1... 第 1 秒时该显示器显示的数值是 a1，小辉想知道第 x 秒~第 y 秒（包含第 x 秒和第 y 秒），计时器上出现的数值之和是多少？询问有 q 组。

Input Format

第一行，两个正整数 n,q。 
第二行，n 个正整数，为 a1~an。 
接着 q 行，每行两个正整数 x,y
【数据范围】  
20%的数据，n,q<=100,ai<=1000,1<=x<=y<=1000  
60%的数据，n,q<=10000,ai<=1000,1<=x<=y<=1000000  
100%的数据，n,q<=100000,ai<=1000,1<=x<=y<=1000000000000 

Output Format

q 行，每行一个正整数，表示第 x 秒~第 y 秒计时器上出现的数字之和

5 3
11 12 13 14 15
1 2
2 3
1 10

23
25
130

Hint

【样例解释】 前 10 秒的数值为：11—>12—>13—>14—>15—>11—>12—>13—>14—>15 

Source

南海区镇赛 桂城小学2022B 前缀和 强基-数学思维