Problem Description

Ctholly gives you a sequence $a$. In each query, you are given an interval $[l, r]$. You need to count the number of pairs $(i, j)$ such that $l \le i < j \le r$, and the binary representation of $a_i \oplus a_j$ contains exactly $k$ ones. Here, $\oplus$ means bitwise XOR.

Input Format

The first line contains three integers $n$, $m$, and $k$.

The second line contains $n$ integers representing the sequence $a$.

Then follow $m$ lines. Each line contains two integers $l$ and $r$, representing one query.

Output Format

Output $m$ lines, each containing one integer, which is the answer to the corresponding query.

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

0
1
2
3
4

Hint

For $5\%$ of the testdata, it is the sample.

For $30\%$ of the testdata, $1 \le n, m \le 5000$.

For $50\%$ of the testdata, the memory limit is 512 MiB.

For $100\%$ of the testdata, it is guaranteed that $1 \le n, m \le 10^5$, and $0 \le a_i, k < 2^{14}$.

Translated by ChatGPT 5