Description

A restaurant has $n$ dishes, numbered $1, 2, \ldots, n$. The evaluation value of dish $i$ is $a_i$. There are $m$ customers. The $i$-th customer's expected value is $b_i$, and their preference value is $x_i$. Therefore, the $i$-th customer considers the deliciousness of dish $j$ to be $b_i \oplus (a_j + x_i)$, where $\oplus$ denotes the XOR operation.

The $i$-th customer wants to pick the dish they consider the most delicious, i.e., the one with the maximum deliciousness value, but due to price and other factors, they can only choose from dishes $l_i$ through $r_i$. Please help them find the most delicious dish.

Input Format

The first line contains two integers $n, m$, the number of dishes and the number of customers.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, the evaluation value of each dish.

Lines $3$ to $m + 2$ each contain four integers $b, x, l, r$, indicating the customer's expected value, preference value, and the allowed range of dishes.

Output Format

Output $m$ lines, each containing one integer, the maximum deliciousness value chosen by that customer.

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

9 
7 
6 
7

Hint

Constraints.

For $100\%$ of the testdata, it holds that $1 \le n \le 2 \times 10^5$, $0 \le a_i, b_i, x_i < 10^5$, $1 \le l_i \le r_i \le n$ ($1 \le i \le m$), $1 \le m \le 10^5$.

Translated by ChatGPT 5