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

题目描述

珂朵莉给了你一个序列 $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$ 行,每行一个数表示查询的结果。

输入输出样例

输入样例 #1

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

输出样例 #1

0
1
2
3
4

说明

对于5%的数据,为样例。 对于30%的数据,$1 \leq n , m \leq 5000$。 对于50%的数据,空间限制为 512 MiB。 对于100%的数据,$1 \leq n, m \leq 100000$,$0 \leq a_i, k < 16384$。