benny-and-queries-marcheasy

View Russian Translation

Probably, you have already read some problems but you still have not met any problems with queries on segments. Therefore Benny wants to fix it.

She gives you an array A of N elements.  And then you have to answer Q queries.

Each query consists of three integers L, R, X. Your task is to find such Ai, that L ≤ i ≤ R and Ai xor X is maximal. For each query output the maximum of Ai xor X.

Input format

The first line contains two integers N and Q.
The next line contains N integers Ai.
The next Q lines contain three integers L, R, X.

Output format

For each query output the maximum of Ai xor X in a single line.

Constraints
1 ≤ N, Q ≤ 5 * 10^5
0 ≤ Ai < 2^20
1 ≤ L ≤ R ≤ N
0 ≤ X < 2^20
1 ≤ N, Q ≤ 3 * 10^3 holds for test cases worth 15% of the problem's score.
1 ≤ N, Q ≤ 10^5 holds for test cases worth 60% of the problem's score.

SAMPLE INPUT
5 3
1 7 3 8 2
1 5 10
3 4 6
2 5 8

SAMPLE OUTPUT
13
14
15

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: String algorithms

Greedy algorithms


Solutions: