Защита окружающей среды
Арсеник и Цианид Майнинг (ACM) — это корпорация, которая недавно решила начать разработку своих шахт на землях возле вашего родного города. Ваша задача как члена комитета гражданского регулирования операций ACM — контролировать, сколько корпорация может добывать с этих земель, чтобы сохранить рабочие места и другие преимущества, не жертвуя при этом окружающей средой и здоровьем местных жителей.
ACM планирует разрабатывать несколько прямоугольных участков земли. Участок земли имеет ширину W, может быть выкопан до максимальной глубины D и имеет плоскую поверхность, которую мы считаем на глубине 0. Минералы на участке организованы в три слоя, которые могут варьироваться по глубине вдоль ширины участка, но всегда имеют одинаковый профиль по всей длине. Именно поэтому ACM интересуется только профилем вдоль ширины каждого участка и провела разведочные работы, чтобы точно определить его форму. В результате они обнаружили, что две границы между тремя слоями минералов могут быть представлены двумя функциями y_1(x) и y_2(x), где первая описывает границу между верхним и средним слоями, а вторая — между средним и нижним слоями. Эти функции всегда таковы, что
-D < y_2(x) < y_1(x) < 0 для 0 ≤ x ≤ W,
так что границы слоев никогда не соприкасаются. Кроме того, каждая функция имеет вид y_i(x) = p_i(x)/q_i(x), где
и ,
для i = 1, 2 и некоторого целого числа K. На рисунке ниже показаны профили двух участков земли в том виде, в котором их представляет ACM. Участок слева имеет ширину W=6 и глубину D=9, в то время как участок справа имеет W=8 и D=10. Границы слоев каждого участка описываются функциями, определенными под ними.
ACM выкопает все на участке земли до определенной глубины копания d, а затем продаст все полученные минералы, чтобы получить прибыль. Однако минералы в верхнем и нижнем слоях практически не имеют ценности, поэтому прибыль от всей операции исходит исключительно от минералов в среднем слое. Фактически, прибыль пропорциональна площади A среднего слоя в профиле, находящегося на глубине не более d. Учитывая описание участка земли и целое число A, вы хотели бы знать глубину копания d, которую вы должны разрешить ACM выкопать участок, чтобы они получили площадь минералов из среднего слоя в профиле ровно A. На рисунке выше вы можете увидеть ответ для двух тестовых случаев в примере ввода. Для участка слева, чтобы получить площадь A=4, глубина копания должна быть d=4.00000, а для участка справа площадь A=14 требует глубины копания d=5.51389.
Входные данные
Каждый тестовый случай описывается с использованием пяти строк. Первая строка содержит четыре целых числа W, D, A и K, где W — это ширина участка земли, который ACM хочет разрабатывать (1 ≤ W ≤ 8), D — его глубина (1 ≤ D ≤ 10), A — это площадь среднего слоя в профиле, которую ACM должна получить (1 ≤ A ≤ W×D), а K позволяет определить интерфейсы y_1(x) и y_2(x), как объяснено выше (0 ≤ K ≤ 8). Каждая из других строк содержит K+1 целых чисел от -10^8 до 10^8 включительно. Вторая строка содержит коэффициенты p_1(x) от P_{1,0} до P_{1,K}. Третья строка содержит коэффициенты q_1(x) от Q_{1,0} до Q_{1,K}. Четвертая строка содержит коэффициенты p_2(x) от P_{2,0} до P_{2,K}. Пятая строка содержит коэффициенты q_2(x) от Q_{2,0} до Q_{2,K}. В пределах каждого тестового случая A строго меньше общей площади среднего слоя в профиле, и существует единственное значение d, такое что глубина копания d дает площадь минералов из среднего слоя в профиле ровно A. Кроме того, q_1(x)=0, q_2(x)=0 и -D < y_2(x) < y_1(x) < 0, для 0 ≤ x ≤ W.
Выходные данные
Для каждого тестового случая выведите строку с рациональным числом, представляющим глубину d, на которую ACM следует разрешить выкопать участок земли, чтобы они получили площадь минералов из среднего слоя в профиле ровно A. Результат должен быть выведен как рациональное число с ровно пятью знаками после запятой, округленное при необходимости.