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≤i,j≤r such that ai⊕aj has exactly k ones in its binary representation.
### Input
- The first line contains three integers n,q,k.
- The second line contains n integers ai.
- 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≤n,q≤105.
- 0≤ai,k<214.
### Example
Input:
552348024535142515
Output:
01234
