Description
小辉制作了一个显示器，该显示器显示的数值 a1、a2、a3...an 是一开始就植入的,并会按照次序依次循环显示，每秒变化 1 次。也就是说，该显示器显示的数值是按照以下规律变化的：a1—>a2—>a3...—>an—>a1—>a2...—>an—>a1... 第 1 秒时该显示器显示的数值是 a1，小辉想知道第 x 秒~第 y 秒（包含第 x秒和第 y 秒），计时器上出现的数值之和是多少？询问有 q 组。
Input
第一行，两个正整数 n,q。
第二行，n 个正整数，为 a1~an。
接着 q 行，每行两个正整数 x,y。
Output
q 行，每行一个正整数，表示第 x 秒~第 y 秒计时器上出现的数字之和。
5 3
11 12 13 14 15
1 2
2 3
1 10
HINT
【样例解释】
前 10 秒的数值为：11—>12—>13—>14—>15—>11—>12—>13—>14—>15
【数据范围】
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