Given an array $a$ consisting of $n$ integers. There are $q$ queries of the form $(l, r)$. For each query, count the number of pairs $l \le i,j \le r$ such that $a_i \oplus a_j$ has exactly $k$ ones in its binary representation.
### Input
- The first line contains three integers $n, q, k$.
- The second line contains $n$ integers $a_i$.
- The next $q$ lines each contain two integers $l, r$.
### Output
- For each query, print an integer representing the number of valid pairs.
### Constraints
- $1 \le n, q \le 10^5$.
- $0 \le a_i, k < 2^{14}$.
### Example
Input:
```
5 5 2
3 4 8 0 2
4 5
3 5
1 4
2 5
1 5
```
Output:
```
0
1
2
3
4
```
