Sunset 和 Elephant 正在对一个序列 $b_1, b_2, \dots, b_m$ 进行游戏。两名玩家轮流行动，Sunset 先手。在每一轮中，当前玩家选择序列开头或结尾的一个值，将其加入该玩家的得分，并从序列中移除该值。当序列为空时游戏结束。两名玩家都希望最大化自己的得分，并且会采取最优策略。

给定一个序列 $a_1, a_2, \dots, a_n$ 和 $q$ 次询问。在第 $i$ 次询问中，给定两个整数 $l_i$ 和 $r_i$。请编写一个程序，计算当他们选择 $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$ 作为初始序列 $b$ 时游戏的最终结果。这里 $m = r_i - l_i + 1$，且对于每个 $1 \le j \le m$，都有 $b_j = a_{l_i+j-1}$。

输入格式

每个测试点仅包含一组测试数据。

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 100\,000, 1 \le q \le 200\,000$)，分别表示序列的长度和询问次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)，表示询问。

保证所有 $a_i$ 的值都是从区间 $[1, 10^9]$ 中的整数均匀随机选择的。随机性条件不适用于样例测试，但你的程序必须能够通过样例。

输出格式

对于每次询问，输出一行，包含两个整数 $S$ 和 $E$，分别表示 Sunset 的最终得分和 Elephant 的最终得分。

样例

输入 1

5 4
7 9 3 5 2
1 5
3 5
2 4
1 2

输出 1

12 14
5 5
12 5
9 7