Tommy and Alan decide to celebrate ~\mathrm e~-day by doing some calculus problems with their ~Q~ friends!

There are ~N~ problems, and the ~i~-th problem gives ~d_i~ points. The ~j~-th person has a difficulty adjustment of ~m_j~, which means that the ~i~-th problem has an adjusted difficulty of ~m_j \oplus i~. Additionally, the ~j~-th person can only solve problems which have an adjusted difficulty of at most ~k_j~. That is, the ~j~-th person can solve the ~i~-th problem if ~m_j \oplus i \le k_j~.

For each of the ~Q~ people, can you figure out, over all the problems they can solve, which will give them the most points?

~\oplus~ stands for the bitwise XOR operator (e.g. ~0110 \oplus 1010 = 1100~).

Input Specification

The first line contains two space-separated integers ~N~ and ~Q~.

The second line contains ~N~ space-separated integers ~d_0, d_1, \dots, d_{N-1}~ ~(1 \le d_i \le 10^6)~.

The next ~Q~ lines each contain the description of one of Tommy and Alan's friends. Each query contains two space-separated integers ~m_j~ ~(0 \le m_j < N)~ and ~k_j~.

The following table shows how the available 15 marks are distributed.

Mark Awarded	Number of Problems	Number of Queries	Additional Constraints
~3~ marks	~1 \le N \le 10^3~	~1 \le Q \le 10^3~	~1 \le k_j \le 10^3~
~3~ marks	~1 \le N \le 10^5~	~1 \le Q \le 10^5~	~1 \le k_j \le 10^6~
~9~ marks	~1 \le N \le 10^6~	~1 \le Q \le 5 \times 10^5~	~1 \le k_j \le 10^6~

Output Specification

For each person, output the number of points of the hardest problem they can solve. It can be proven that at least one problem is always possible.

Sample Input 1

5 2
1 2 3 4 5
1 3
2 4

Output for Sample Input 1

4
4

Explanation of Output for Sample Input 1

Person ~1~ can do problems ~0~, ~1~, ~2~, and ~3~. Of those, problem ~3~ gives the most points, ~4~.

Person ~2~ can also gain ~4~ points by doing problem ~3~.

Sample Input 2

8 2
9 3 5 6 6 2 4 3
2 5
6 1

Output for Sample Input 2

9
4

Explanation of Output for Sample Input 2

Person ~1~ can do problems ~0~, ~1~, ~2~, ~3~, and ~6~. Problem ~0~ gives ~9~ points, which is the highest.

Person ~2~ can score ~4~ points by doing problem ~6~.