Sequence Walk Query

You are given a sequence of n integers \(a_1, a_2, \ldots, a_n\).

Then, there are q queries. In each query, you are given three integers \(x, l, r\). You start with the number \(x\) and traverse the sequence from index \(l\) to index \(r\) (1-indexed). At each position \(i\) during the traversal, you update \(x\) as follows:

\(x = \max\bigl(x, a_i - x\bigr)\)

Your task is to output the final value of \(x\) after processing each query.

inputFormat

The first line contains two integers \(n\) and \(q\) (the length of the sequence and the number of queries).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the sequence.

Then \(q\) lines follow. Each of these lines contains three integers \(x, l, r\) describing one query.

Note: The indices of the sequence are 1-indexed.

outputFormat

For each query, output one line containing the final value of \(x\) after processing the query.

sample

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

3
2