Захист довкілля
Видобуток миш'яку та ціаніду (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. Результат має бути виведений як раціональне число з точністю до п'яти знаків після коми, округлене за потреби.