Description

Jim是一个热爱打游戏的小伙子，可惜他的游戏水平不太行，以至于经常在游戏里被别人欺负。而且Jim不仅游戏玩的菜，他还很爱喷人，但是由于自己的垃圾操作，他又喷不过别人。为了改善这种局面，Jim决定成为一个腿部挂件（俗称抱大腿）。
已知现在有\(N\)个选手可供Jim选择，每位选手的能力值为 \(a_i\)。\(N\)位选手不一定每位选手都有时间配Jim玩游戏而且Jim的状态也时好时坏，所以Jim有\(Q\)个询问，每个询问是\(3\)个数\(X\)、\(L\)、\(R\)，求第\(L\)个人到第\(R\)个人这\(R-L+1\)个人中与Jim配合后的能力值最大是多少，Jim与第\(i\)位选手配合后的能力值为\(a_i\)与\(X\)进行异或运算（Xor）。

Format

Input

第1行：2个数\(N\), \(Q\)中间用空格分隔，分别表示选手个数及查询的数量\((1≤N≤200000, 1≤Q≤200000)\)。
第2行：共\(N\)个数为每个选手能力值中间用空格分隔，对应\(a_i(0≤a[i]≤10^9)\)。
第N+2 - N+Q+1行：每行3个数\(X\), \(L\), \(R\)，中间用空格分隔。\((0≤X≤10^9，0≤L≤R<N)\)

Output

输出共\(Q\)行，对应每次询问所能得到的最大能力值。

Sample 1

Input

9 8
2 15 4 12 0 6 0 16 12
2 2 5
4 8 8
16 5 8
16 6 8
1 0 5
12 3 4
15 1 1
5 0 4

Output

14
8
28
28
14
12
0
10

Limitation

2s, 256MiB for each test case.

Hint

样例解释

对于第一个询问 \(2\) 与\(\{4 \; 12 \; 0\}\) 最大的能力值组合为 \(2 \; xor \; 12 = 14\) 注意 \(L\) \(R\)标号从 \(0\) 开始

数据范围

对于20%的数据保证\((1≤N≤5000, 1≤Q≤5000)\)。
对于45%的数据保证\((1≤N≤50000, 1≤Q≤50000)\)。
对于100%的数据保证\((1≤N≤200000, 1≤Q≤200000)\)。

Source

CSP 2019 模拟测试题（三）