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

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

【数据范围】

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