定义 op 操作意义为将当前数除以 d 并向下取整.
SY 现在有 m 个“原数”，若一个数经过若干次 op 操作(包括 0 次)后能变为这个“原数”，那么这个数是可以被这个“原数”所消灭的。注意，“原数”是不会被消耗的.
现在 SY 想问你,对于一个区间 [l,r]，在消灭最多个数的前提下最少需要多少个“原数”？

第一行 4 个数,分别是 n,m,d,q,分别表示数列 {a} 元素个数，SY 拥有的 “原数” 个数，op 操作参数，询问个数。
第二行为 {a} 数列，即需要被消灭的数列。
第三行为 m 个“原数”。
接下来 q 行，每行两个数 l 和 r，表示询问区间为 [l,r]。

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

样例二：
输入：
6 3 3 3
6 5 10 15 19 7
2 5 10
1 6
1 4
4 6
输出：
3
3
2

数据结构 Trie