Problem Background

SY finally managed to solve the math problem given by QM, and while having lunch, QM filled her mind with a fantasy bubble... SY popped it open and found another long sequence of numbers!

SY really doesn't want to think anymore, so she decides to use elementary division to eliminate the numbers in her mind.

Problem Description

Define the operation $op$ as dividing the current number by $d$ and rounding down.

SY now has $m$ "original numbers". If a number can be transformed into one of these "original numbers" through a series of $op$ operations (including zero times), then this number can be eliminated by that "original number". Note that "original numbers" are not consumed.

SY wants to know, for a given interval $[l, r]$, what is the minimum number of "original numbers" needed to eliminate the maximum number of numbers?

Input Format

The first line contains four numbers: $n, m, d, q$, representing the number of elements in the sequence $\{a\}$, the number of "original numbers" SY has, the parameter for the $op$ operation, and the number of queries, respectively.

The second line is the sequence $\{a\}$, the sequence of numbers to be eliminated.

The third line contains $m$ "original numbers".

The next $q$ lines, each containing two numbers $l$ and $r$, represent the query interval $[l, r]$.

Output Format

For each query in order, output an integer on a new line representing the answer.

Sample Input and Output

Sample Input #1

2 3 3 3
0 20
6 6 6
1 1
2 2
1 2

Sample Output #1

0
1
1

Sample Input #2

6 3 3 3
6 5 10 15 19 7
2 5 10
1 6
1 4
4 6

Sample Output #2

3
3
2

Notes

Sample Explanation:

Sample 1: $20$ can be transformed into $6$ through one $op$ operation (dividing by $3$ and rounding down), while $0$ cannot be transformed into $6$ through any number of $op$ operations.

Thus, the interval $[1,1]$ can eliminate a maximum of $0$ numbers, requiring $0$ "original numbers" to do so. The intervals $[1,2]$ and $[2,2]$ can eliminate a maximum of $1$ number, requiring $1$ "original number" to do so.

Sample 2: $2$ can eliminate $\{6, 19, 7\}$, $5$ can eliminate $\{5, 15\}$, and $10$ can eliminate $\{10\}$. Therefore, the intervals $[1,6]$ and $[1,4]$ can be fully eliminated using all "original numbers", and the interval $[4,6]$ can be fully eliminated using $2$ and $5$.

Data Range:

For $30\%$ of the data: $n \leq 100, m \leq 10, d = 2, q \leq 10$

For $100\%$ of the data: $n \leq 5 \times 10^5, m \leq 60, 2 \leq d \leq 10, q \leq 10^6, 0 \leq a_i, b_i \leq 2^{63}$

Special Property: The data is specially constructed.

见题面 Input 部分

见题面 Output 部分