你有一个长度为 $n$ 的序列，其中第 $i$ 个元素的值为 $a_i$。

现在有 $q$ 组询问，每组询问给定 $x,l,r$，表示你刚开始有一个数字 $x$ ，然后你从序列的第 $l$ 个位置走到第 $r$ 个位置，每经过一个位置就执行 $x=\max(x,a_i-x)$。你需要回答每组询问最后 $x$ 的值。

输入格式

第一行两个整数 $n$ 和 $q$，分别表示序列长以及询问数量。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示序列第 $i$ 个元素的值 $a_i$。

接下来 $q$ 行，每行三个整数 $x,l,r$，含义如题目描述中所示。

输出格式

输出 $q$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i$ 组询问的答案。

样例数据

样例输入

10 6
1 4 6 2 10 -3 1 0 13 4
2 1 10
0 5 10
5 1 10
0 4 8
-2 6 9
7 2 9

样例输出

7
10
8
8
11
7

子任务

Idea：zx2003，Solution：zx2003，Code：zx2003，Data：zx2003

样例解释

对于第一组询问，$x$ 的值为 $2(初始)→2→2→4→4→6→6→6→6→7→7(最终)$。

限制与约定

对于所有数据，保证 $ 1\leq n,q\leq 2\times 10^5,1\leq l \leq r \leq n，0\leq |x|,|a_i|\leq 10^{13}$。