Description

定义 $op$ 操作意义为将当前数除以 $d$ 并向下取整.

SY 现在有 $m$ 个“原数”，若一个数经过若干次 $op$ 操作(包括 $0$ 次)后能变为这个“原数”，那么这个数是可以被这个“原数”所消灭的。注意，“原数”是不会被消耗的.

现在 SY 想问你,对于一个区间 $[l,r]$，在消灭最多个数的前提下最少需要多少个“原数”？

Input Format

第一行 $4$ 个数,分别是 $n,m,d,q$,分别表示数列 $\{a\}$ 元素个数，SY 拥有的 “原数” 个数，$op$ 操作参数，询问个数。

第二行为 $\{a\}$ 数列，即需要被消灭的数列。

第三行为 $m$ 个“原数”。

接下来 $q$ 行，每行两个数 $l$ 和 $r$，表示询问区间为 $[l,r]$。

Output Format

按照询问顺序，每一行输出一个整数表示答案.

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

0
1
1

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

3
3
2

Hint

样例解释：

#样例1 ： $20$ 经过一次 $op$ 操作（除以 $3$ 向下取整）可以变成 $6$，而 $0$ 不能经过若干次 $op$ 操作变成 $6$ 。

所以区间 $[1,1]$ 最多消灭 $0$ 个数，消灭最多数前提下最少需要 $0$ 个 "原数"，区间 $[1,2],[2,2]$ 最多消灭 $1$ 个数，消灭最多数前提下最少需要 $1$ 个 "原数" 。

#样例2 ： $2$ 能消灭 $\{6,19,7\}$ ， $5$ 能消灭 $\{5,15\}$ ， $10$ 能消灭 $\{10\}$ ， 所以区间 $[1,6],[1,4]$ 最少能用所有 "原数" 全部消灭，区间 $[4,6]$ 能用 $2,5$ 全部消灭。

数据范围：

对于 $30\%$ 的数据：$n\le100,m\leq10, d=2, q\le 10$

对于 $100\%$ 的数据：$n\le5\times 10^{5},m\leq60,2\leq d\leq10,q\le10^{6},0\le a_i,b_i< 2^{63}$

特殊性质：数据经过构造。