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 A_i, that L ≤ i ≤ R and A_i xor X is maximal. For each query output the maximum of A_i xor X.

Input format

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

Output format

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

Constraints

• 1 ≤ N, Q ≤ 5 * 10⁵
• 0 ≤ A_i < 2²⁰
• 1 ≤ L ≤ R ≤ N
• 0 ≤ X < 2²⁰
• 1 ≤ N, Q ≤ 3 * 10³ holds for test cases worth 15% of the problem's score.
• 1 ≤ N, Q ≤ 10⁵ holds for test cases worth 60% of the problem's score.