题目描述

显示器按 $a_1,a_2,\ldots,a_n$ 循环显示，每秒一个数，第1秒显示 $a_1$。多次询问第 $x$ 秒至第 $y$ 秒（含两端）显示的数之和。

输入格式

第一行 $n,q$；第二行 $n$ 个数；接下来 $q$ 行各 $x,y$。

输出格式

每个询问输出一行答案。

样例

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

23
25
130

数据范围

20%的数据：$n,q\le100$，$y\le1000$。

60%的数据：$n,q\le10000$，$y\le10^6$。

100%的数据：$1\le n,q\le100000$，$1\le a_i\le1000$，$1\le x\le y\le10^{12}$。