题目描述

珂朵莉给了你一个序列 $a$，每次查询给一个区间 $[l,r]$，查询 $l \leq i< j \leq r$，且 $a_i \oplus a_j$ 的二进制表示下有 $k$ 个 $1$ 的二元组 $(i,j)$ 的个数。$\oplus$ 是指按位异或。

输入格式

第一行三个数表示 $n,m,k$。

第二行 $n$ 个数表示序列 $a$。

之后 $m$ 行，每行两个数 $l,r$ 表示一次查询。

输出格式

输出 $m$ 行，每行一个数表示查询的结果。

5 5 2
3 4 8 0 2
4 5
3 5
1 4
2 5
1 5

0
1
2
3
4

提示

对于 $5\%$ 的数据，为样例。

对于 $30\%$ 的数据，$1 \leq n , m \leq 5000$。

对于 $50\%$ 的数据，空间限制为 512 MiB。

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^5$，$0 \leq a_i, k < 2^{14}$。