Давайте немного отвлечёмся от красно-чёрных деревьев, перенесёмся в любимое кафе Рудольфа и выясним, почему же Рудольф так долго трапезничал. Кафе работает по принципу шведского стола: можно выбирать любые блюда, а затем подходить к кассе и оплачивать их. Имеются две кассы, к каждой из которых ведёт отдельная очередь.
Рудольф зашёл в кафе и понял, что попал как раз в обеденное время — у обеих касс были огромные очереди.
Будучи грамотным математиком, Рудольф сразу же посчитал, что в первой очереди n1 человек, а во второй — n2. Следуя логике, он встал в очередь с наименьшим количеством людей. Спустя некоторое время он понял, что очереди двигаются с разными скоростями, поэтому выбор наименьшей очереди вовсе не означал, что Рудольф быстрее оплатит свой обед. Рудольф заметил, что скорость обслуживания зависит от возраста обслуживаемого человека — старшему поколению гораздо сложнее разобраться с хитроумными устройствами безналичной оплаты, чем молодым людям. Рудольф разделил всех людей на категории в соответствии с их возрастом. Для каждой категории Рудольф определил время обслуживания на кассе:
Поскольку Рудольф хочет как можно быстрее оплатить свой обед, он решил, что каждую минуту с вероятностью p он будет переходить в другую очередь, если она на момент принятия решения состоит из меньшего числа людей.
Рудольфу стало интересно, чему равно математическое ожидание количества переходов между очередями за период времени с момента занятия очереди в кафе до момента оплаты обеда. Давайте поможем ему в решении этой задачи.
Считать, что остальные люди не перемещаются между очередями, а также что в очередях не появляются новые люди.
Первая строка содержит вещественное число p (0 ≤ p ≤ 1), заданное не более чем с 6 знаками после десятичной точки, — вероятность перехода Рудольфа из одной очереди в другую.
Вторая строка содержит целое число n1 (1 ≤ n1 ≤ 100) — количество людей в первой очереди.
Третья строка содержит n1 целых чисел a1i (18 ≤ a1i ≤ 100) — возраст людей в первой очереди в порядке обслуживания.
Четвертая строка содержит целое число n2 (1 ≤ n2 ≤ 100, n2 ≠ n1) — количество людей во второй очереди.
Пятая строка содержит n2 целых чисел a2j (18 ≤ a2j ≤ 100) — возраст людей во второй очереди в порядке обслуживания.
Выведите одно вещественное число — математическое ожидание количества переходов между очередями, которые может совершить Рудольф при заданных условиях. Абсолютная или относительная погрешность ответа не должна превышать 10 - 6.
## Входные Данные
Первая строка содержит вещественное число p (0 ≤ p ≤ 1), заданное не более чем с 6 знаками после десятичной точки, — вероятность перехода Рудольфа из одной очереди в другую. Вторая строка содержит целое число n1 (1 ≤ n1 ≤ 100) — количество людей в первой очереди.Третья строка содержит n1 целых чисел a1i (18 ≤ a1i ≤ 100) — возраст людей в первой очереди в порядке обслуживания.Четвертая строка содержит целое число n2 (1 ≤ n2 ≤ 100, n2 ≠ n1) — количество людей во второй очереди.Пятая строка содержит n2 целых чисел a2j (18 ≤ a2j ≤ 100) — возраст людей во второй очереди в порядке обслуживания.
## Выходные Данные
Выведите одно вещественное число — математическое ожидание количества переходов между очередями, которые может совершить Рудольф при заданных условиях. Абсолютная или относительная погрешность ответа не должна превышать 10 - 6.
## Примеры
Входные данные1.0170518 18 18 18 18Выходные данные1.000000000Входные данные1.0318 70 18518 18 18 18 18Выходные данные1.000000000Входные данные0.5318 18 18218 18Выходные данные0.000000000Входные данные0.5320 50 30418 30 40 18Выходные данные0.750000000
[samples]
**Definitions**
Let $ p \in [0, 1] $ be the probability of switching queues at each minute.
Let $ n_1, n_2 \in \mathbb{Z}^+ $, $ n_1 \ne n_2 $, be the initial number of people in queues 1 and 2, respectively.
Let $ A_1 = (a_{1,1}, a_{1,2}, \dots, a_{1,n_1}) $ and $ A_2 = (a_{2,1}, a_{2,2}, \dots, a_{2,n_2}) $ be sequences of ages in queues 1 and 2, respectively.
Define service times:
For each person with age $ a $, service time is $ s(a) = \begin{cases} 2 & \text{if } a \ge 60 \\ 1 & \text{otherwise} \end{cases} $.
Let $ T_1 = \sum_{i=1}^{n_1} s(a_{1,i}) $ be the total service time of queue 1.
Let $ T_2 = \sum_{j=1}^{n_2} s(a_{2,j}) $ be the total service time of queue 2.
Let $ t_{\text{end}} = \min(T_1, T_2) $ be the time at which Rudolph finishes payment (when the queue he is in is fully served).
Rudolph initially joins the queue with fewer people. If $ n_1 < n_2 $, he starts in queue 1; else in queue 2.
At each integer minute $ t \in \{1, 2, \dots, t_{\text{end}} - 1\} $, if the remaining number of people in the *other* queue is strictly less than in his current queue, he switches to it with probability $ p $.
Let $ X $ be the random variable denoting the total number of queue switches.
**Objective**
Compute $ \mathbb{E}[X] $.