Description
珂朵莉给了你一个序列 a，每次查询给一个区间 [l,r]，查询 l≤i<j≤r，且 ai⊕aj 的二进制表示下有 k 个 1 的二元组 (i,j) 的个数。⊕ 是指按位异或。
Input
第一行三个数表示 n,m,k。
第二行 n 个数表示序列 a。
之后 m 行，每行两个数 l,r 表示一次查询。
Output
输出 m 行，每行一个数表示查询的结果。
5 5 2
3 4 8 0 2
4 5
3 5
1 4
2 5
1 5
HINT
对于5%的数据，为样例。
对于30%的数据，1≤n,m≤5000。
对于50%的数据，空间限制为 512 MiB。
对于100%的数据，1≤n,m≤100000，0≤ai,k<16384。