题目描述

点击查看pdf

MianKing has a sequence $a_{1...n}$ and he wants to answer $Q$ queries about it.

Let $f(a,S,K)$ denote the K-th smallest number of sequence $b_{1...n}$ which satisfies that $\\forall i \\in [1,n], b_i=a_i~xor~S$.

Now for each query, give you $L,R,K$, you need to answer $Min_{S=L}^{R}f(a,S,K)$.

输入格式

The first line has two integers $n,Q$.

The second line has $n$ integers which denote $a_{1...n}$.

Then there are $Q$ lines, the i-th line has three integers $L,R,K$ which represents the i-th query.

$1\\leq n,Q\\leq 10^5$

$0\\leq a_i<2^{30}$

$0\\leq L\\leq R<2^{30}$

$1\\leq K\\leq n$

输出格式

There are $Q$ lines, the i-th line has one integer which denotes $Min_{S=L}^{R}f(a,S,K)$.

样例

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

0 
1 
2 

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

3 
0 
2 
5 

提示

Form 2020ICPC济南站