给定一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ 以及一个整数 $k$。
现在要进行 $m$ 次询问，每次询问给定一个区间 $[l,r]$，请你求出共有多少个数对 $(i,j)$ 满足 $l \le i < j \le r$ 且 $a_i \oplus a_j$ 的结果在二进制表示下恰好有 $k$ 个 $1$。
注：$\oplus$ 表示按位异或操作。
第一行包含三个整数 $n,m,k$。
第二行包含 $n$ 个整数表示 $a_1,a_2,…,a_n$。
接下来 $m$ 行，每行包含两个整数 $l,r$，表示一次询问。
共 $m$ 行，每行输出一个查询的结果。
$1 \le n,m \le 10^5$,
$0 \le k \le 14$,
$0 \le a_i < 2^{14}$,
$1 \le l < r \le n$
5 3 2
1 1 4 7 7
1 5
1 3
3 5