题目描述

小辉制作了一个显示器，该显示器显示的数值 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

样例解释

样例中显示器的循环序列为[11,12,13,14,15]，共有3组询问：

1. 第1秒~第2秒显示的数值依次是11、12，求和得11+12=23；
2. 第2秒~第3秒显示的数值依次是12、13，求和得12+13=25；
3. 第1秒~第10秒显示的数值依次是11、12、13、14、15、11、12、13、14、15，求和得(11+12+13+14+15)×2=75×2=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。