L. Subxor
time limit per test
1 с
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a_1,a_2,\dots,a_n$$$, you need to answer multiple queries raised by Mr. Wor, who is interested in understanding specific aspects of the array.

Each query consists of two integers $$$l$$$ and $$$r~(1 \leq l \leq r \leq n)$$$. You need to find the longest contiguous subarray of $$$a_l, a_{l+1},\dots,a_r$$$, such that the XOR sum of its elements is less than or equal to a given value $$$K$$$.

Specifically, you need to find a pair $$$u,v$$$ and maximize the value of $$$v - u + 1$$$, subject to the conditions as follows:

$$$$$$ \begin{align} & l \leq u \leq v \leq r \\

a_u \oplus & a_{u+1} \oplus \cdots \oplus a_{v} \leq K \\

\end{align} $$$$$$

Note that the value of $$$K$$$ is predetermined and remains constant for all queries. If there exists no valid pair $$$u,v$$$, then output $$$0$$$.

Please write a program for Mr. Wor to answer all the queries correctly.

Input

The first line contains $$$2$$$ integers $$$n,K~(1 \leq n \leq 2 \times 10^4, 0 \leq K \lt 2^{31})$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n~(0 \leq a_i \lt 2^{31})$$$, denoting the array.

The third line contains one integer $$$q~(1 \leq q \leq 2 \times 10^4)$$$, denoting the number of queries.

In the next $$$q$$$ lines, each line contains $$$2$$$ integers $$$l,r~(1 \leq l \leq r \leq n)$$$, describing a query.

Output

For each query, print one integer in one line, denoting the maximum length of the subarray. Print $$$0$$$ if such subarray doesn't exist.

Example
Input
5 1
1 2 3 4 5
4
1 5
2 4
3 4
3 5
Output
5
2
0
2