P5629 【AFOI-19】区间与除法

SY 好不容易才解出 QM 给她的数学题，在恰午饭的时候，QM 向她的脑洞里塞了个幻想的泡泡……SY 戳开一看，又是长长的一串数字！ SY 实在是不想思考了，她决定用小学的除法消灭她脑洞里的数字。

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

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

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

#### 样例解释： **#样例 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 \le 100,m \le 10, d=2, q \le 10$； 对于 $100\%$ 的数据：$n \le 5 \times 10^{5},m \le 60,2 \le d \le 10,q \le 10^{6},0 \le a_i,b_i< 2^{63}$。  特殊性质：数据经过构造。