Dish Selection

A restaurant offers \(n\) dishes numbered from \(1\) to \(n\), where the \(i\)-th dish has a rating of \(a_i\). There are \(m\) customers. The \(i\)-th customer has an expectation value \(b_i\) and a preference value \(x_i\). The perceived deliciousness of the \(j\)-th dish for the \(i\)-th customer is defined as

[ b_i \oplus (a_j + x_i), ]

where \(\oplus\) denotes the bitwise XOR operation.

Each customer can only choose from a subset of dishes, specifically those with indices from \(l_i\) to \(r_i\) (inclusive). For each customer, determine the maximum deliciousness value among the allowed dishes.

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of dishes and the number of customers, respectively.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the ratings of the dishes.

Then follow \(m\) lines. The \(i\)-th of these lines contains four integers \(b_i, x_i, l_i, r_i\), where \(b_i\) and \(x_i\) are the expectation and preference values for the \(i\)-th customer, and \(l_i\) and \(r_i\) denote the range of dish indices from which the customer can choose.

outputFormat

For each customer, output a single line containing one integer: the maximum deliciousness value calculated as \(b_i \oplus (a_j+x_i)\) over all dishes with indices \(j\) in the range \(l_i \leq j \leq r_i\).

sample

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

7
7
15