A restaurant has $n$ dishes, numbered $1 \dots n$. The value of the $i$-th dish is $a_i$ ($1 \le i \le n$).

There are $m$ customers. The $i$-th customer has an expected value $b_i$ and a preference value $x_i$. Therefore, the $i$-th customer considers the deliciousness of the $j$-th dish to be $b_i \oplus (a_j + x_i)$, where $\oplus$ denotes the bitwise XOR operation.

The $i$-th customer wants to choose the dish they consider most delicious, i.e., the dish with the maximum deliciousness value. However, due to factors such as price, they can only choose from dishes in the range $[l_i, r_i]$.

Please help them find the most delicious dish.

Input

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

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

The next $m$ lines each contain four integers, $b, x, l, r$, representing the expected value, preference value, and the range of dishes the customer can choose from.

Output

Output $m$ lines, each containing one integer, $y_{max}$, representing the maximum deliciousness value for that customer.

Examples

Input 1

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

Output 1

9
7
6
7

Constraints

For all data, $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$).

For 30% of the data, $1 \le m \le 10^3$.

For 100% of the data, $1 \le m \le 10^5$.