题目描述

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

输入格式

第一行，两个正整数 n,q。 第二行，n 个正整数，为 a1~an。 接着 q 行，每行两个正整数 x,y

输出格式

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

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

23
25
130

数据规模与约定

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

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