题目描述
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
输入格式
见题面
输出格式
见题面