XOR k-th Smallest

Problem Description

You are given $n$ numbers $a_1, a_2, \dots, a_n$.

You must answer $m$ queries. Each query gives two numbers $x$ and $k$, and asks for the $k$-th smallest element among $a_1 \oplus x, a_2 \oplus x, \dots, a_n \oplus x$ (sorted in ascending order).

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

The following $m$ lines each contain two numbers $x$ and $k$ ($1 \le k \le n$), representing one query.

Output Format

Output $m$ lines in total, each containing one integer: the $k$-th smallest value for that query.

Sample Input

5 5
11 10 6 4 14
15 1
11 4
3 5
6 1
9 1

Sample Output

1
13
13
0
2

Constraints

For $100\%$ of the test data: $1 \le n, m \le 2 \times 10^5$, $0 \le a_i, x \le 2^{30} - 1$.