Count Pairs with XOR Condition

Given a sequence of positive integers \(a_1, a_2, \dots, a_n\) of length \(n\) and a constant \(x\), you are to answer \(q\) queries. In each query, you are given an interval \([l, r]\). Your task is to count the number of pairs \((i, j)\) with \(l \le i < j \le r\) such that

[ a_i \oplus a_j \le x, ]

where \(\oplus\) denotes the bitwise XOR operation.

inputFormat

The first line contains three integers \(n\), \(q\), and \(x\) separated by spaces.

The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\) separated by spaces.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) defining a query interval.

outputFormat

For each query, output a single line containing the number of pairs \((i, j)\) such that \(i < j\) and \(a_i \oplus a_j \le x\).

sample

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

2
2