下山市是一个卧虎藏龙的地方。这天 hehe 蚤在公园散步的时候，就遇到了一位真正的卡牌大师 —— QAQ 蚤。

卡牌一共 $n$ 张，垒成了一摞，从上到下用 $1$ 到 $n$ 编号。此外，第 $i$ 张牌上还写着一个整数 $a_i$。

QAQ 蚤和 hehe 蚤一共会进行 $q$ 局卡牌游戏。其中，第 $i$ 局卡牌游戏流程如下：

1. QAQ 蚤抽出编号在 $l_i$ 到 $r_i$ 的卡牌，以同样的顺序垒成一摞。

2. QAQ 蚤和 hehe 蚤轮流行动，每次取走剩余卡牌中的任意一张，直到牌全部被取完。其中 QAQ 蚤为先手。

3. 两人的得分分别是各自得到的卡牌上的整数之和。

4. 最后，QAQ 蚤把牌按原来的顺序放回牌堆。

hehe 蚤是一位稳健型选手。由于牌都是背面朝上，hehe 蚤无法知道卡牌上的整数，也不会尝试记忆那些曾经抽到过的卡。

因此 hehe 蚤取卡牌时，总会使用一个非常稳健的策略——取走剩余卡牌中编号最小的一张。

但 QAQ 蚤早就记下了所有卡牌上的整数。并且他绝顶聪明，早就看出了 hehe 蚤是一位稳健型选手，每次只会拿走编号最小的卡。

在知晓上述信息的情况下，QAQ 蚤会设计策略，最大化自己的得分。

当然，作为一位真正的卡牌大师，QAQ 蚤提前算出了自己每局的得分。然而他发现你在一旁看热闹，于是要求你也算出这些得分，来验证自己算出的结果。

输入格式

第一行两个数 $n,q$，表示牌堆大小和游戏次数。

第二行 $n$ 个数 $a_i$，表示每张卡牌上的整数。

然后 $q$ 行，每行两个数，$l_i,r_i$，表示第 $i$ 局游戏抽出牌的编号区间。

输出格式

输出 $q$ 行，每行一个整数，表示第 $i$ 局 QAQ 蚤的得分。

样例一

input

5 3
3 4 1 2 5
1 3
2 5
1 5

output

5
9
11

explanation

考虑第三局游戏。

第一轮 QAQ 蚤取 $a_2 = 4$，hehe 蚤取 $a_1 = 3$，

第二轮 QAQ 蚤取 $a_4 = 2$，hehe 蚤取 $a_3 = 1$，

第三轮 QAQ 蚤取 $a_5 = 5$。

QAQ 蚤取的总和为 $4+2+5=11$，可以证明不存在更优方案。

样例二

见附加文件中 ex_game2.in 与 ex_game2.ans，该组样例满足子任务 1,2,4,5 的性质。

样例三

见附加文件中 ex_game3.in 与 ex_game3.ans，该组样例满足子任务 3 的性质。

样例四

见附加文件中 ex_game4.in 与 ex_game4.ans，该组样例满足子任务 5 的性质。

限制与约定

对于 $100\%$ 数据，$1\le n,q\le 2\times10^5,1\le a_i\le 10^9,1\le l_i\le r_i\le n$。

时间限制：$3\texttt{s}$

空间限制：$512\texttt{MB}$