暂无测试数据。

蒜头君有一个长度为 $n$ 的非负整数数列 $a_i$。

现在共有 $q$ 次询问，每次询问会给出三个正整数 $l, r, m$。对于每次询问，蒜头君需要找到一个非负整数 $k$，满足 $k < 2^m$，并且使得数列 $a$ 中区间 $[l, r]$ 内的所有数的异或和再与 $k$ 异或的结果最大，即 $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r \oplus k$ 的结果最大。

对于每次询问，输出 $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r \oplus k$ 的最大异或和。

注：$x\oplus y$ 表示的是 $x$ 异或 $y$，在 C++ 中异或使用^符号。

输入格式

第一行输入两个以空格隔开的正整数 $n,q$，分别表示数列的长度和询问的次数。

第二行输入 $n$ 个以空格隔开的非负整数 $a_i$，数列中的第 $i$ 个数为 $a_i$。

接下来 $q$ 行，每行输入 $3$ 个以空格隔开的正整数 $l,r,m$，表示的每次询问的区间为 $[l,r]$，以及 $k$ 的限制条件 $m$。

输出格式

输出共 $q$ 行，第 $i$ 行输出一个非负整数，表示第 $i$ 个询问的最大异或和。

数据范围

对于 $30\%$ 的数据，$1\leq n,q \leq 1000,m = 1$；

对于另外 $20\%$ 的数据，$1\leq n,q \leq 10^5,m = 1$；

对于另外 $20\%$ 的数据，$1\leq n,q \leq 1000, l = r,2\leq m \leq 31$;

对于 $100\%$ 的数据，$1\leq n,q \leq 10^5,0\leq a_i \leq (2^{31} -1),1\leq l \leq r \leq n,1\leq m \leq 31$。

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

3
7
1

5 4
1 2 0 4 8
1 2 8
2 5 15
3 4 13
1 5 12

255
32767
8191
4095