题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 以及一个整数 $x$。

接下来有 $m$ 次询问，每次询问给你两个整数 $l$ 和 $r$，你需要回答出下标区间 $[l, r]$ 是否存在两个元素 $a_i$ 和 $a_j$ 满足它们的异或和为 $x$（即判断是否存在两个下标 $i$ 和 $j$ 满足 $l \le i \lt j \le r$ 且 $a_i \oplus a_j = x$，这里 $\oplus$ 是异或符号）。

输入格式

第一行，三个整数 $n,m,x$，以空格分隔（$2 \le n \le 10^5, 1 \le m \le 10^5, 0 \le x \lt 2^{20}$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，两两之间以一个空格分隔（$0 \le a_i \lt 2^{20}$）。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，以一个空格分隔，表示一次询问（$1 \le l \lt r \le n$）。

输出格式

对于每次询问，输出一行。如果下标区间 $[l, r]$ 内不存在异或和为 $x$ 的两个元素，输出 yes；否则，输出 no。

样例

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

yes
no
yes
no

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 1000, x \lt 2^{10}$
• 对于 $100\%$ 的数据，$n,m \le 10^5, x \lt 2^{20}$