MianKing 有一个序列 $a_{1 \dots n}$，他想要回答关于该序列的 $Q$ 个查询。

令 $f(a, S, K)$ 表示序列 $b_{1 \dots n}$ 中的第 $K$ 小的数，其中序列 $b$ 满足 $\forall i \in [1, n], b_i = a_i \oplus S$。

现在对于每个查询，给定 $L, R, K$，你需要回答 $\min_{S=L}^R f(a, S, K)$。

输入格式

第一行包含两个整数 $n, Q$。 第二行包含 $n$ 个整数，表示 $a_{1 \dots n}$。 接下来有 $Q$ 行，第 $i$ 行包含三个整数 $L, R, K$，表示第 $i$ 个查询。

$1 \le n, Q \le 10^5$ $0 \le a_i < 2^{30}$ $0 \le L \le R < 2^{30}$ $1 \le K \le n$

输出格式

输出 $Q$ 行，第 $i$ 行包含一个整数，表示 $\min_{S=L}^R f(a, S, K)$。

样例

输入 1

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

输出 1

0
1
2

输入 2

5 4
0 1 2 3 4
2 3 4
4 5 1
2 2 3
1 4 5

输出 2

3
0
2
5