你有一个长度为 $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}$。
| 子任务编号 | $n,q\leq$ | 特殊性质 | 子任务分值 |
|---|---|---|---|
| $1$ | $1000$ | 无 | $8$ |
| $2$ | $80000$ | $-500\leq x,a_i\leq 500$ | $16$ |
| $3$ | $2\times10^5$ | $10^6\leq x,a_i\leq 10^6$ 且 $l=1$ | $25$ |
| $4$ | $2\times10^5$ | $l=1$ | $24$ |
| $5$ | $2\times10^5$ | 无 | $27$ |