CF925A.Stairs and Elevators

In the year of $30XX$ participants of some world programming championship live in a single large hotel. The hotel has $n$ floors. Each floor has $m$ sections with a single corridor connecting all of them. The sections are enumerated from $1$ to $m$ along the corridor, and all sections with equal numbers on different floors are located exactly one above the other. Thus, the hotel can be represented as a rectangle of height $n$ and width $m$. We can denote sections with pairs of integers $(i, j)$, where $i$ is the floor, and $j$ is the section number on the floor.

The guests can walk along the corridor on each floor, use stairs and elevators. Each stairs or elevator occupies all sections $(1, x)$, $(2, x)$, $\ldots$, $(n, x)$ for some $x$ between $1$ and $m$. All sections not occupied with stairs or elevators contain guest rooms. It takes one time unit to move between neighboring sections on the same floor or to move one floor up or down using stairs. It takes one time unit to move up to $v$ floors in any direction using an elevator. You can assume you don't have to wait for an elevator, and the time needed to enter or exit an elevator is negligible.

You are to process $q$ queries. Each query is a question "what is the minimum time needed to go from a room in section $(x_1, y_1)$ to a room in section $(x_2, y_2)$?"

在 $30XX$ 年，某世界编程锦标赛的参赛者们全部居住在一家大型酒店中。该酒店共有 $n$ 层楼，每层楼有 $m$ 个区域，所有区域沿一条公共走廊依次排列。各区域沿走廊编号为 $1$ 至 $m$；不同楼层上编号相同的区域恰好上下对齐。因此，整座酒店可表示为一个高为 $n$、宽为 $m$ 的矩形。我们用二元组 $(i, j)$ 表示某个区域，其中 $i$ 为楼层号，$j$ 为该楼层上的区域编号。

宾客可在同一楼层的走廊中自由行走，也可使用楼梯或电梯。每部楼梯或电梯占据所有形如 $(1, x), (2, x), \ldots, (n, x)$ 的区域，其中 $x$ 为 $1$ 到 $m$ 之间的某个整数。所有未被楼梯或电梯占据的区域均为客房。在同一楼层中从一个区域移动到相邻区域，或通过楼梯上下一层楼，均需耗时 $1$ 个时间单位。而使用电梯上下最多 $v$ 层楼（任意方向）也仅需 $1$ 个时间单位。你可以假设无需等待电梯，且进出电梯所需时间可忽略不计。

你需要处理 $q$ 个查询。每个查询的形式为：“从区域 $(x_1, y_1)$ 内的一间客房出发，到达区域 $(x_2, y_2)$ 内的一间客房，所需的最短时间是多少？”

The first line contains five integers $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$) — the number of floors and section on each floor, the number of stairs, the number of elevators and the maximum speed of an elevator, respectively.

The second line contains $c_l$ integers $l_1, \ldots, l_{c_l}$ in increasing order ($1 \leq l_i \leq m$), denoting the positions of the stairs. If $c_l = 0$, the second line is empty.

The third line contains $c_e$ integers $e_1, \ldots, e_{c_e}$ in increasing order, denoting the elevators positions in the same format. It is guaranteed that all integers $l_i$ and $e_i$ are distinct.

The fourth line contains a single integer $q$ ($1 \leq q \leq 10^5$) — the number of queries.

The next $q$ lines describe queries. Each of these lines contains four integers $x_1, y_1, x_2, y_2$ ($1 \leq x_1, x_2 \leq n$, $1 \leq y_1, y_2 \leq m$) — the coordinates of starting and finishing sections for the query. It is guaranteed that the starting and finishing sections are distinct. It is also guaranteed that these sections contain guest rooms, i. e. $y_1$ and $y_2$ are not among $l_i$ and $e_i$.

第一行包含五个整数 $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$），表示该次查询的起点与终点房间坐标。保证起点与终点房间不同，且这两个房间均为客房（即 $y_1$ 和 $y_2$ 均不等于任一 $l_i$ 或 $e_i$）。

Print $q$ integers, one per line — the answers for the queries.

输出 $q$ 个整数，每个整数占一行——即各查询的答案。

In the first query the optimal way is to go to the elevator in the 5-th section in four time units, use it to go to the fifth floor in two time units and go to the destination in one more time unit.

In the second query it is still optimal to use the elevator, but in the third query it is better to use the stairs in the section 2.

在第一次查询中，最优方案是用 4 个时间单位到达第 5 区域的电梯，再用 2 个时间单位乘坐电梯到达第 5 层，最后再用 1 个时间单位到达目的地。

在第二次查询中，使用电梯仍是最优方案；但在第三次查询中，在第 2 区域使用楼梯更优。