A. Лестницы и лифты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В $$$30XX$$$ году участников чемпионата мира по спортивному ориентированию поселили в одном огромном отеле. Отель состоит из $$$n$$$ этажей. Каждый этаж разбит на $$$m$$$ отсеков, соединенных одним длинным коридором. Если пронумеровать отсеки каждого этажа от $$$1$$$ до $$$m$$$ в порядке перемещения по коридору, то все отсеки с одинаковыми номерами будут находиться строго друг под другом. Таким образом, отель можно представлять себе в виде прямоугольника высоты $$$n$$$ и ширины $$$m$$$. Отсеки будем описывать парами чисел $$$(i, j)$$$, где $$$i$$$ — номер этажа, $$$j$$$ — номер отсека на этаже.

Гости могут перемещаться между по коридорам между отсеками одного этажа, а также по лестницам и лифтам между этажами. Каждая лестница либо лифт занимает все отсеки $$$(1, x)$$$, $$$(2, x)$$$, $$$\ldots$$$, $$$(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}$$$ в возрастающем порядке ($$$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$$$.

Выходные данные

Выведите $$$q$$$ целых чисел по одному на строке — ответы на запросы.

Пример
Входные данные
5 6 1 1 3
2
5
3
1 1 5 6
1 3 5 4
3 3 5 3
Выходные данные
7
5
4
Примечание

В первом запросе оптимальный путь — дойти до лифта в отсеке 5 за четыре единицы времени, подняться на пятый этаж за две единицы времени и прийти на финиш за еще одну единицу.

Во втором запросе выгоднее также воспользоваться лифтом, а в третьем запросе — лестницей в отсеке 2.