题目描述

小辉制作了一个显示器，该显示器显示的数值 $a_1 , a_2 , a_3 ... , a_n$ 是一开始就植入的,并会按照次序依次循环显示，每秒变化 1 次。也就是说，该显示器显示的数值是按照以下规律变化的: $a_1$ -> $a_2$ -> $a_3$ ->... -> $a_n$ -> $a_1$ -> $a_2$ -> $a_n$ -> $a_1$ ......

第 1 秒时该显示器显示的数值是 $a_1$，小辉想知道第 x ~ 第 y 秒(包合第 x 秒和第 y 秒)，计时器上出现的数值之和是多少?询问有 q 组。

输入格式

第一行，两个正整数 n , q 。

第二行，n 个正整数，为 $a_1$ ~ $a_n$

接着 q 行，每行两个正整数 x , y

数据范围

20% 的数据，n , q <= 100 , $a_i$ <= 1000, 1 <= x <= y <= 1000

60% 的数据，n , q <= 10000 , $a_i$ <= 1000 , 1 <= x <= y <= 1000000

100% 的数据，n , q <= 100000 , $a_i$ <= 1000 , 1 <= x <= y <= 1000000000000

输出格式

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

样例

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

23
25
130

样例解释

前 10 秒的数值为: 11 -> 12 -> 13 -> 14 -> 15 -> 11 -> 12 -> 13 -> 14 -> 15