F. Subset AND
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a_1, a_2, ..., a_n$$$, and two integers $$$k$$$ and $$$q$$$. Please answer the following $$$q$$$ queries:

For each query, you are given two integers $$$l$$$ and $$$r$$$. Your task is to determine whether there exists a nonempty subset of $$$\{a_l, a_{l + 1}, ..., a_r\}$$$ whose bitwise AND is equal to exactly $$$k$$$.

We define the bitwise AND of a nonempty integer subset $$$\{b_1, b_2, ..., b_m\}$$$ to be $$$b_1$$$ if $$$m = 1$$$, and $$$b_1 \text{ AND } b_2 \text{ AND } ... \text{ AND } b_m$$$ otherwise.

Input

The first line of input consists of three space-separated integers $$$n$$$, $$$k$$$, and $$$q$$$ $$$(1 \leq n, q \leq 2 \cdot 10^5$$$, $$$0 \leq k \lt 2^{30})$$$.

The second line consists of $$$n$$$ space-separated integers $$$a_1, a_2, ..., a_n$$$ $$$(0 \leq a_i \lt 2^{30})$$$.

The next $$$q$$$ lines each consist of two space-separated integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$.

Output

Output $$$q$$$ lines. On the $$$i$$$th line, output YES if the answer to the $$$i$$$th query is yes, and NO otherwise.

Examples
Input
5 2 3
1 6 10 0 2
1 3
1 2
3 5
Output
YES
NO
YES
Input
10 2 10
2 10 6 8 14 7 13 6 9 8
2 7
5 6
1 6
4 8
4 10
2 7
6 8
2 8
5 8
1 1
Output
YES
NO
YES
NO
NO
YES
NO
YES
NO
YES
Note

In the first sample test case, the answer to the first query is YES, since $$$6 \text{ AND } 10 = 2$$$.

There is no nonempty subset of $$$\{1, 6\}$$$ with AND equal to $$$2$$$, so the answer to the second query is NO.

For the third query, the subset $$$\{2\}$$$ can be picked.