Subset AND
Description
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.
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 < 2^{30})$.
The second line consists of $n$ space-separated integers $a_1, a_2, ..., a_n$ $(0 \leq a_i < 2^{30})$.
The next $q$ lines each consist of two space-separated integers $l$ and $r$ $(1 \leq l \leq r \leq n)$.
Output $q$ lines. On the $i$th line, output YES if the answer to the $i$th query is yes, and NO 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 < 2^{30})$.
The second line consists of $n$ space-separated integers $a_1, a_2, ..., a_n$ $(0 \leq a_i < 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.
5 2 3
1 6 10 0 2
1 3
1 2
3 5
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
YES
NO
YES
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.