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)$?"


-----Input-----

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


-----Output-----

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


-----Example-----
Input
5 6 1 1 3
2
5
3
1 1 5 6
1 3 5 4
3 3 5 3

Output
7
5
4



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
def takeClosest(myList, myNumber):

    """

    Assumes myList is sorted. Returns closest value to myNumber.



    If two numbers are equally close, return the smallest number.

    """

    if len(myList) == 0:

        return 9e10

    pos = bisect_left(myList, myNumber)

    if pos == 0:

        return myList[0]

    if pos == len(myList):

        return myList[-1]

    before = myList[pos - 1]

    after = myList[pos]

    if after - myNumber < myNumber - before:

       return after

    else:

       return before



from bisect import bisect_left

from math import ceil



n, m, n_stairs, n_elevators, v = map(int, input().split(" "))



if n_stairs > 0:

    stairs = list(map(int, input().split(" ")))

else:

    stairs = []

    input()

if n_elevators > 0:

    elevators = list(map(int, input().split(" ")))

else:

    elevators = []

    input()

queries = int(input())

res = []

for i in range(queries):

    x1, y1, x2, y2 = map(int, input().split(" "))

    next_elevator = takeClosest(elevators, (y1 + y2) / 2)

    next_stairs = takeClosest(stairs, (y1 + y2) / 2)

    time_elevator = abs(x1 - x2) / v

    time_stairs = abs(x1 - x2)



    mi = min(y1, y2)

    ma = max(y1, y2)

    if next_elevator < mi:

        time_elevator += (mi - next_elevator) * 2

    elif next_elevator > ma:

        time_elevator += (next_elevator - ma) * 2



    if next_stairs < mi:

        time_stairs += (mi - next_stairs) * 2

    elif next_stairs > ma:

        time_stairs += (next_stairs - ma) * 2



    dis = abs(y1 - y2)

    if time_elevator < time_stairs:

        dis += time_elevator

    else:

        dis += time_stairs

    if x1 == x2:

        res.append(abs(y1 - y2))

    else:

        res.append(ceil(dis))

print(*res, sep="\n")



# Made By Mostafa_Khaled

import sys
input=sys.stdin.readline
import math
import bisect
n,m,cl,ce,v=list(map(int,input().split()))
l=[int(i) for i in input().split() if i!='\n' ]
e=[int(i) for i in input().split() if i!='\n']
q=int(input())
for i in range(q):
        x1,y1,x2,y2=list(map(int,input().split()))
        lft,neareststa,sta,nearestele=0,0,0,0
        if x2==x1 and y1==y2:
            output=0
        elif x2==x1:
            output=abs(y2-y1)
        else:
            lft=math.ceil(abs((x2-x1))/v)
            #print(lft)
            sta=abs(x2-x1)
            if cl>0:
                nearestele=bisect.bisect_left(l,y1)
                if len(l)>nearestele:
                    first=abs(l[nearestele]-y1)+abs(y2-l[nearestele])
                else:
                    first=1000000000001
                if nearestele!=0:
                    second=abs(l[nearestele-1]-y1)+abs(y2-l[nearestele-1])
                else:
                    second=1000000000001
                #print(first,second,nearestele)
                nearestele=min(first,second)
            else:
                nearestele=1000000000001
            if ce>0:
                neareststa=bisect.bisect_left(e,y1)
                #print('n',neareststa)
                if len(e)>neareststa:
                    first=abs(e[neareststa]-y1)+abs(y2-e[neareststa])
                    #print(first)
                else:
                    first=1000000000001
                if neareststa!=0:
                    second=abs(e[neareststa-1]-y1)+abs(y2-e[neareststa-1])
                else:
                    second=1000000000001
                neareststa=min(first,second)
            else:
                neareststa=1000000000001
            #print(lft,sta,neareststa,nearestele,first,second)
            output=min(lft+neareststa,sta+nearestele)
    
        sys.stdout.write(str(output)+'\n')



import sys
input=sys.stdin.readline
import math
import bisect
n,m,cl,ce,v=list(map(int,input().split()))
l=[int(i) for i in input().split() if i!='\n' ]
e=[int(i) for i in input().split() if i!='\n']
q=int(input())
for i in range(q):
        x1,y1,x2,y2=list(map(int,input().split()))
        lft,neareststa,sta,nearestele=0,0,0,0
        if x2==x1 and y1==y2:
            output=0
        elif x2==x1:
            output=abs(y2-y1)
        else:
            lft=math.ceil(abs((x2-x1))/v)
            sta=abs(x2-x1)
            if cl>0:
                nearestele=bisect.bisect_left(l,y1)
                if len(l)>nearestele:
                    first=abs(l[nearestele]-y1)+abs(y2-l[nearestele])
                else:
                    first=1000000000001
                if nearestele!=0:
                    second=abs(l[nearestele-1]-y1)+abs(y2-l[nearestele-1])
                else:
                    second=1000000000001
                nearestele=min(first,second)
            else:
                nearestele=1000000000001
            if ce>0:
                neareststa=bisect.bisect_left(e,y1)
                if len(e)>neareststa:
                    first=abs(e[neareststa]-y1)+abs(y2-e[neareststa])
                else:
                    first=1000000000001
                if neareststa!=0:
                    second=abs(e[neareststa-1]-y1)+abs(y2-e[neareststa-1])
                else:
                    second=1000000000001
                neareststa=min(first,second)
            else:
                neareststa=1000000000001
            output=min(lft+neareststa,sta+nearestele)
        sys.stdout.write(str(output)+'\n')