You are given a sequence of length $n$, where the $i$-th element is $a_i$.

There are $q$ queries. Each query provides $x, l, r$, meaning you start with a number $x$ and traverse the sequence from index $l$ to $r$. For each position $i$ visited, you update $x$ by performing $x = \max(x, a_i - x)$. You need to output the final value of $x$ for each query.

Input

The first line contains two integers $n$ and $q$, representing the length of the sequence and the number of queries, respectively.

The second line contains $n$ integers, where the $i$-th integer is the value $a_i$ of the $i$-th element of the sequence.

The next $q$ lines each contain three integers $x, l, r$, as described in the problem statement.

Output

Output $q$ lines, each containing one integer, where the $i$-th line represents the answer to the $i$-th query.

Examples

Input 1

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

Output 1

7
10
8
8
11
7

Note

For the first query, the value of $x$ changes as follows: $2 (\text{initial}) \to 2 \to 2 \to 4 \to 4 \to 6 \to 6 \to 6 \to 6 \to 7 \to 7 (\text{final})$.

Constraints

For all data, it is guaranteed that $1 \leq n, q \leq 2 \times 10^5$, $1 \leq l \leq r \leq n$, and $0 \leq |x|, |a_i| \leq 10^{13}$.