You are given an array A of N elements and Q queries to answer.

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 ≤ 10^5