P4887 [Template] Mo's Algorithm Second-Order Offline / The 14th Block Decomposition (Prototype).

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.

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 $m$ lines, each containing one integer, which is the answer to the corresponding query.

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