Guan 国的贫富差距正在急剧增大!

为了了解具体情况, 国王 Guanyue1234 请你在全国进行了调研。

现在你得到了一个共有 n 个数字的数列 a, 代表你调查的 n 个人的经济状况，数字越大说明受访者越富裕。

国王需要你将数列 a 从大到小排序, 然后回答他的 m 个询问。

每个询问将给出两个正整数 l 和 r, 你需要输出排序后的 a[l] 到 a[r] 间所有数字的和。

数据保证对于每一个询问, 答案必小于 2^{31} 。

输入的第一行包含 2 个正整数 n, m, 分别表示数列 a 中数字的个数和询问数。

接下来一行共有 n 个非负整数, 表示数列 a 中的每个数。数列从 1 开始编号。

接下来 m 行, 每行两个整数 l 和 r, 表示询问的区间, 1 \leq l \leq r \leq n 

输出包括 m 行, 每行 1 个整数, 表示每个询问的结果。

对于 100 \% 的数据, 有 1 \leq n \leq 10^{6}, 1 \leq m \leq 10^{3} 。

| 测试点 | n | m | 约定 |

| :---: | :---: | :---: | :---: |

| 1,2,3 | \leq 10^{4} | \leq 500 | 数列 a 从大到小按顺序给出 |

| 4 | \leq 10^{5} | \leq 10^{3} | 数列 a 从大到小按顺序给出 |

| 5,6 | \leq 10^{4} | \leq 500 | 无 |

| 7,8 | \leq 10^{5} | \leq 10^{3} | 无 |

| 9,10 | \leq 10^{6} | \leq 10^{3} | 无 |