CF925A Stairs and Elevators

在 $30XX$ 年，某世界编程锦标赛的参赛选手们齐聚在一座巨大的酒店。酒店共有 $n$ 层楼，每层楼有 $m$ 个区域，它们通过一条走廊相连。每层的区域从 $1$ 到 $m$ 进行编号，且在不同楼层中编号相同的区域位于正上方。因此，整栋酒店可以看作是一个高为 $n$ 且宽为 $m$ 的矩形结构。我们用整数对 $(i, j)$ 来表示各个区域，其中 $i$ 是楼层编号，$j$ 是该楼层的区域编号。 客人可以在每层楼的走廊上行走，也能通过楼梯和电梯到达其他楼层。每部楼梯或电梯占据了从 $(1, x)$ 到 $(n, x)$ 的所有区域，这里 $x$ 介于 $1$ 和 $m$ 之间。所有未被楼梯或电梯占用的区域是客房。 在同一楼层内相邻区域间的移动需要花费一个时间单位，使用楼梯上下楼层同样需要一个时间单位。使用电梯可以在任意方向上最多跨越 $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}$，表示楼梯的位置。如果 $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$ 不会在楼梯或电梯的位置中出现。

输出 $q$ 个整数，每行一个，表示每个查询的最短时间。 **本翻译由 AI 自动生成**

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.