Routine Execution Count

LS has set up (n) routines. The (i)-th routine is initiated at time (a_i). For the (i)-th routine, starting from time (a_i), LS executes it every (k) seconds (i.e. at times (a_i,, a_i+k,, a_i+2k, \dots)). The execution time is negligible. You are given (m) queries. Each query is represented by a time interval ([l_i, r_i]) and you need to determine the total number of routine executions performed by LS in that time interval (inclusive).

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) (the number of routines, the number of queries, and the interval in seconds between consecutive executions, respectively).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) where \(a_i\) is the starting time of the \(i\)-th routine.

The next \(m\) lines each contain two integers \(l_i\) and \(r_i\) representing a query for the time interval \([l_i, r_i]\).

outputFormat

For each query, output a single integer representing the total number of routine executions in the given time interval.

sample

2 3 3
1 2
1 3
2 6
5 10

2
3
3