Absolute Difference Transformation

You are given a sequence a of length n. Each element is used in a transformation operation defined by \( x = |x - a_i| \). You will be given multiple queries; each query provides a range \([l, r]\) and an initial value \(v\). For each query, process the elements in the sequence from index \(l\) to \(r\) (1-indexed) sequentially, updating \(v\) as follows:

[ v = |v - a_i| \quad \text{for } i = l, l+1, \ldots, r. ]

Your task is to output the final value of \(v\) after the entire transformation for each query.

inputFormat

The first line contains an integer \(n\) indicating the length of the sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, ..., a_n\).

The third line contains an integer \(q\) representing the number of queries.

Each of the next \(q\) lines contains three integers \(l\), \(r\), and \(v\), where \(l\) and \(r\) are the bounds of the query (1-indexed) and \(v\) is the initial value for the transformation.

outputFormat

For each query, output a single line with the final value of \(v\) after processing the query.

sample

5
3 1 4 1 5
3
1 5 10
2 4 3
1 3 0

4
1
2