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

题目描述

珂朵莉给了你一个序列 $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%的数据,空间限制为512MB 对于100%的数据,$1 \leq n , m \leq 100000 , 0 \leq ai , k < 16384$