在 $$$30XX$$$ 年,一些世界编程锦标赛的参与者住在一家大酒店里。酒店有 $$$n$$$ 楼层。每层楼都有 $$$m$$$ 区域,并有一条走廊连接所有区域。走廊沿线的区域从 $$$1$$$ 到 $$$m$$$ 依次排列,不同楼层上所有相同编号的区域都精确地位于另一个区域的上方。因此,酒店可以表示为高度 $$$n$$$ 和宽度 $$$m$$$ 的矩形。我们可以用整数对 $$$(i, j)$$$ 来表示区域,其中 $$$i$$$ 是楼层,$$$j$$$ 是楼层上的区域编号。
客人可以沿着各楼层的走廊行走,使用楼梯和电梯。每个楼梯或电梯占据所有部分 $$$(1, x)$$$、$$$(2, x)$$$、$$$\ldots$$$、$$$(n, x)$$$(对于 $$$1$$$ 和 $$$m$$$ 之间的某些 $$$x$$$。所有没有楼梯或电梯的区域都包含客房。在同一层的相邻区域之间移动或使用楼梯向上或向下移动一层需要一个时间单位。使用电梯向任意方向移动到 $$$v$$$ 楼层需要一个时间单位。您可以假设您不必等待电梯,并且进出电梯所需的时间可以忽略不计。
您将处理 $$$q$$$ 查询。每个查询都是一个问题“从 $$$(x_1, y_1)$$$ 部分的房间到 $$$(x_2, y_2)$$$ 部分的房间需要的最短时间是多少?”
输入
第一行包含五个整数 $$$n, m, c_l, c_e, v$$$ ($$$2 \leq n, m \leq 10^8$$$, $$$0 \leq c_l, c_e \leq 10^5$$$, $$$1 \leq c_l + c_e \leq m - 1$$$, $$$1 \leq v \leq n - 1$$$) — 分别为楼层数和每层的区域数、楼梯数、电梯数和电梯最大速度。
第二行包含 $$$c_l$$$ 整数 $$$l_1, \ldots, l_{c_l}$$$ 按升序排列 ($$$1 \leq l_i \leq m$$$),表示楼梯的位置。如果$$$c_l = 0$$$,则第二行为空。
第三行包含 $$$c_e$$$ 整数 $$$e_1, \ldots, e_{c_e}$$$ 按升序排列,以相同的格式表示电梯位置。保证所有整数 $$$l_i$$$ 和 $$$e_i$$$ 是不同的。
第四行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行描述查询。每行包含四个整数 $$$x_1, y_1, x_2, y_2$$$ ($$$1 \leq x_1, x_2 \leq n$$$, $$$1 \leq y_1, y_2 \leq m$$$) - 查询的开始和结束部分的坐标。确保开始和结束部分是不同的。还保证这些部分包含客房,即。 e. $$$y_1$$$ 和 $$$y_2$$$ 不在 $$$l_i$$$ 和 $$$e_i$$$ 之中。
输出
打印 $$$q$$$ 个整数,每行一个 - 查询的答案。
示例
输入 #1
5 6 1 1 3 2 5 3 1 1 5 6 1 3 5 4 3 3 5 3
输出 #1
7 5 4
注意
在第一个查询中,最佳方式是用四个时间单位去第五段的电梯,用它用两个时间单位去五楼,再用一个时间单位去目的地。
在第二个查询中,使用电梯仍然是最佳选择,但在第三个查询中,第 2 部分中最好使用楼梯。