XOR Pairs Query

Given a sequence \(a\) of integers. You are to answer \(q\) queries. In each query, an interval \([l, r]\) is given, and you need to count the number of pairs \((i, j)\) that satisfy \(l \le i < j \le r\) and that the binary representation of \(a_i \oplus a_j\) contains exactly \(k\) ones. Here, \(\oplus\) denotes the bitwise XOR operator.

inputFormat

The first line contains three integers \(n\), \(q\), and \(k\) where \(1 \le n, q \le 10^5\) and \(0 \le k \le 32\). The second line contains \(n\) integers representing the sequence \(a\). Each of the next \(q\) lines contains two integers \(l\) and \(r\) (with \(1 \le l < r \le n\)), describing a query.

outputFormat

For each query, output a single integer that is the number of valid pairs \((i, j)\) in the given interval satisfying the specified condition.

sample

5 3 1
1 2 3 4 5
1 3
2 5
1 5

2
4
6