В \(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 за четыре единицы времени, подняться на пятый этаж за две единицы времени и прийти на финиш за еще одну единицу.
Во втором запросе выгоднее также воспользоваться лифтом, а в третьем запросе — лестницей в отсеке 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 1 1 3
2
5
3
1 1 5 6
1 3 5 4
3 3 5 3
|
7
5
4
|