P4887 【模板】莫队二次离线 / 第十四分块(前体)

珂朵莉给了你一个序列 $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\%$ 的数据，为样例。 对于 $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}$。