A11656 | Stairs and Elevators

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$ .

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

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.