Фронтмэн известной рок-группы Мэд, заработав на выпуске своего последнего альбома целое состояние, купил себе особняк с колоннами и видом на оживленную улицу. Однако в первое же утро в новом доме он столкнулся с тем, что проезжающие мимо на автомобилях фанаты начинают снимать его на камеры своих телефонов, как только он покажется из-за колонн.
Утром Мэд начинает движение из точки (0, - 1) и движется параллельно оси OX со скоростью 1 в течение времени T.
На оси OX расположены N колонн, представляющих собой отрезки шириной W. Для каждого отрезка задана X-координата левой точки Si, x. Отрезки не пересекаются, не касаются друг друга и все концы отрезков находятся в сегменте [0, T] по X-координате.
Бесконечная дорога расположена вдоль координаты Cy параллельно оси OX. По дороге движутся K машин со скоростью Cv. Для каждой машины известна X-координата Ci, x в начальный момент времени.
Колонны — непрозрачные. В некоторый момент времени Мэд попадает в кадр видеокамеры, находящейся в машине, если точку, в которой он находится, можно соединить отрезком с точкой, в которой находится машина, не касаясь и не попадая внутрь ни одного из отрезков, соответствующих колоннам.
В каждой машине находится ровно один фанат с камерой, запись он производит тогда и только тогда, когда Мэд попадает в кадр. Таких периодов может быть несколько, в этом случае и записей у фаната будет несколько. Вечером все фанаты, конечно, выкладывают все свои записи в сеть. Необходимо определить, какое суммарное время будут занимать видеоролики с Мэдом, снятые утром.
В первой строке задано время движения Мэда T (1 ≤ T ≤ 106), ширина колонн W (1 ≤ W ≤ 106), Y-координата дороги Cy (1 ≤ Cy ≤ 106) и скорость машин Cv ( - 106 ≤ Cv ≤ 106).
Во второй строке задано количество колонн N (1 ≤ N ≤ 2000).
В третьей строке заданы N чисел Si, x (0 ≤ Si, x ≤ T - W, Si, x + W < Si + 1, x) — упорядоченные по возрастанию X-координаты левых точек отрезков, соответствующих колоннам. Гарантируется, что отрезки не пересекаются и не касаются друг друга.
В четвёртой строке задано количество машин K (1 ≤ K ≤ 2000).
В пятой строке заданы K чисел Ci, x ( - 1012 ≤ Ci, x ≤ 1012) — упорядоченные по возрастанию X-координаты машин.
Все числа во входных данных целые.
Выведите суммарную длительность всех видеороликов, которые попадут в сеть. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 9.
Взаиморасположение и вектора скоростей Мэда, машин и колонн в начальный момент времени, соответствующие первому тестовому примеру, продемонстрированы на рисунке.
В первом тестовом примере хронометраж видеороликов, снятых в машинах, равен соответственно .
Во втором тестовом примере — .
В третьем тестовом примере — .
## Входные Данные
В первой строке задано время движения Мэда T (1 ≤ T ≤ 106), ширина колонн W (1 ≤ W ≤ 106), Y-координата дороги Cy (1 ≤ Cy ≤ 106) и скорость машин Cv ( - 106 ≤ Cv ≤ 106).Во второй строке задано количество колонн N (1 ≤ N ≤ 2000).В третьей строке заданы N чисел Si, x (0 ≤ Si, x ≤ T - W, Si, x + W < Si + 1, x) — упорядоченные по возрастанию X-координаты левых точек отрезков, соответствующих колоннам. Гарантируется, что отрезки не пересекаются и не касаются друг друга.В четвёртой строке задано количество машин K (1 ≤ K ≤ 2000).В пятой строке заданы K чисел Ci, x ( - 1012 ≤ Ci, x ≤ 1012) — упорядоченные по возрастанию X-координаты машин.Все числа во входных данных целые.
## Выходные Данные
Выведите суммарную длительность всех видеороликов, которые попадут в сеть. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 9.
## Примеры
Входные данные10 1 2 -140 2 5 93-1 4 11Выходные данные18Входные данные5 2 3 -320 35-1 0 8 9 12Выходные данные10Входные данные8 3 2 321 53-3 0 4Выходные данные13.400000000000
## Примечание
Взаиморасположение и вектора скоростей Мэда, машин и колонн в начальный момент времени, соответствующие первому тестовому примеру, продемонстрированы на рисунке.В первом тестовом примере хронометраж видеороликов, снятых в машинах, равен соответственно .Во втором тестовом примере — .В третьем тестовом примере — .
[samples]
**Definitions**
Let $ T \in \mathbb{R} $ be the total time of movement.
Let $ W \in \mathbb{R} $ be the width of each column.
Let $ C_y \in \mathbb{R} $ be the $ y $-coordinate of the road.
Let $ C_v \in \mathbb{R} $ be the constant velocity of each car.
Let $ N \in \mathbb{Z}^+ $ be the number of columns.
Let $ S = (s_1, s_2, \dots, s_N) $ be the ordered sequence of left $ x $-coordinates of columns, with each column occupying the interval $ [s_i, s_i + W] $ on the $ x $-axis.
Let $ K \in \mathbb{Z}^+ $ be the number of cars.
Let $ C = (c_1, c_2, \dots, c_K) $ be the ordered sequence of initial $ x $-coordinates of cars.
Mad starts at $ (0, -1) $ at time $ t = 0 $ and moves with velocity $ (1, 0) $, so his position at time $ t \in [0, T] $ is $ (t, -1) $.
Each car $ i $ starts at $ (c_i, C_y) $ at time $ t = 0 $ and moves with velocity $ (C_v, 0) $, so its position at time $ t $ is $ (c_i + C_v t, C_y) $.
**Constraints**
1. $ 1 \le T \le 10^6 $
2. $ 1 \le W \le 10^6 $
3. $ 1 \le C_y \le 10^6 $
4. $ -10^6 \le C_v \le 10^6 $
5. $ 1 \le N \le 2000 $, $ 0 \le s_i \le T - W $, $ s_i + W < s_{i+1} $
6. $ 1 \le K \le 2000 $, $ -10^{12} \le c_i \le 10^{12} $, $ c_i < c_{i+1} $
**Objective**
For each car $ i \in \{1, \dots, K\} $, define the set of times $ t \in [0, T] $ such that the line segment connecting Mad’s position $ (t, -1) $ and the car’s position $ (c_i + C_v t, C_y) $ does not intersect the interior of any column $ [s_j, s_j + W] \times \{0\} $.
The total recording time is the sum over all cars of the Lebesgue measure (total length) of the set of times $ t \in [0, T] $ for which the line segment between $ (t, -1) $ and $ (c_i + C_v t, C_y) $ is unobstructed by any column.
Compute:
$$
\sum_{i=1}^{K} \mu\left( \left\{ t \in [0, T] \mid \text{segment } \overline{(t, -1), (c_i + C_v t, C_y)} \cap \bigcup_{j=1}^{N} [s_j, s_j + W] \times \{0\} = \emptyset \right\} \right)
$$