P3293 [SCOI2016] Delicious

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.

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 $m$ lines, each containing one integer, the maximum deliciousness value chosen by that customer.

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