Problem Description

Given a sequence $A_{1}, A_{2}, \cdots, A_{n}$ of length $n$ and a non-negative integer $x$, there are $m$ queries. Each query asks whether it is possible to choose two numbers from some interval $[l, r]$ such that their XOR equals $x$.

Input Format

The first line contains three integers $n, m, x$.

The second line contains $n$ integers $A_{1}, A_{2}, \cdots, A_{n}$.

The next $m$ lines each contain two integers $l_{i}, r_{i}$, representing the query interval $\left[l_{i}, r_{i}\right]$.

Output Format

For each query, if there exist two numbers in the interval whose XOR is $x$, output yes; otherwise output no.

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

yes
no
yes
no

Hint

[Sample Explanation]

Obviously, in the entire sequence, only the XOR of 2 and 3 equals 1.

[Test Case Scale and Constraints]

For $20\%$ of the test cases, $1 \leq n, m \leq 100$.

For $40\%$ of the test cases, $1 \leq n, m \leq 1000$.

For all test cases, $1 \leq n, m \leq 10^5$, $0 \leq x<2^{20}$, $1 \leq l_{i} \leq r_{i} \leq n$, and $0 \leq A_{i}<2^{20}$.

Lanqiao Cup 2022 Provincial Contest A Group, Problem D.

Translated by ChatGPT 5