Migrated from Lutece 2748 猫为什么讨厌狗是有理由的

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，菜猫拥有 $n$ 个糖罐，每个糖罐的坚固度为 $a_i$。 肉狗知道了这件事后决定去打开罐头偷吃糖果。 肉狗现在有 $m$ 个钥匙，每个钥匙的型号为 $b_i$，可以帮助肉狗打开坚固度恰好为 $b_i$ 的糖罐。 肉狗的力气为 $d$，对于一个坚固度为 $x$ 的糖罐，肉狗可以不断攻击这个糖罐，每次攻击都可以让糖罐的坚固度 $x$ 变为 $\lfloor \frac{x}{d} \rfloor$, 因为带的钥匙越多，开罐时候动静越大，越容易被菜猫发现，所以肉狗想问你,对于下标为区间 $[l,r]$的糖罐，在打开最多糖罐的前提下，他最少需要带多少钥匙。

Input

第一行四个数,分别是 $n$, $m$, $d$, $Q$，分别表示菜猫拥有的糖罐数量，肉狗拥有的钥匙数量，肉狗的力气大小，肉狗询问你的次数。

第二行为 $n$ 个整数， 第 $i$ 个整数代表第 $i$ 个糖罐的坚固度 $a_i$。

第三行为 $m$ 个整数， 第 $i$ 个整数代表第 $i$ 个钥匙的型号。

接下来 $Q$ 行，每行两个数 $L$ 和 $R$，表示询问的下标区间为 $[L, R]$。

Output

按照询问顺序输出 $Q$ 行，每一行输出一个整数表示对于该区间，肉狗需要带的钥匙的最少数量

Samples

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

Constraints

$1\leq n\leq 5\times10^5,1\leq m\leq 60$ $1\leq Q\leq 1\times10^6$ $2\leq d\leq 10,0\leq a_i, b_i\leq 2^{63}$

Resources

2022 UESTC ICPC Training for Data Structures