Гіфи (слово у множині від гіф) - це об'єкти, схожі на воронки. Визначимо гіф як двомірний об'єкт, заданий послідовністю точок (p_1, p_2, ..., p_n) з наступними умовами:
3 ≤ n ≤ 1000;
Нехайь точка p_i має координати (x_i, y_i). Якщо існує такий індекс c (1 < c < n), що y_1 > y_2 > ... > y_c і y_c < y_c_{+1} < y_c_{+2} < ... < y_n, то p_c називається виступом гіфа;
Для усіх 1 ≤ i < c, x_i < x_c і для усіх c < i ≤ n, x_i > x_c;
Для 1 < i < c кут, на який необхідно повернути p_i_{-1} навколо p_i за годинниковою стрілкою так, щоб точка p_i_{-1} стала колінеарною p_ip_i_{+1}, більше 180 градусів. Аналогічно для c < i < n кут повороту p_i_{-1} навколо p_{i }за годинниковою стрілкою щоб стати колінеарною p_ip_i_{+1}, також більше 180 градусів.
Відрізки, які з'єднують дві сусідні точки, перетинаються між собою лише у своїх кінцях.
Наприклад, на наступному рисунку представлено гіф з шістьмома точками і c = 4:
Послідовність відрізків (p_1p_2, p_2p_3, ..., p_n_{-1}p_n) будемо називати тілом гіфа. Вам задано два гіфа P = (p_1, p_2, ..., p_n) та Q = (q_1, q_2, ..., q_m), де усі x координати p_i цілі невід'ємні числа, а усі x координати q_i цілі додатні числа. Вважаючи, що виступи двох гіфів з'єднані між собою вузькою трубкою, наповнимо гіфи водою. Коли вода почне поступати, гіфи будуть наповнюватись згідно відомих фізичних законів (рівень води в обох гіфах залишається однаковим). Якщо у гіфі P рівень води досягне min(y_1, y_n), то вода почне виливатись з гіфа (те ж саме можна сказати про гіф Q). Ваша програма повинна визначити рівень води у двох гіфах після того як тиди заллють деяку її кількість. Оскільки задача розглядається у двох вимірах, то кількість води вимірюється заповненою площею. Об'єм трубки, яка з'єднує виступи гіфів, вважати рівним нулю.
Перший рядок містить кількість тестів t. Кожен тест задається у трьох рядках. Перший рядок містить одне ціле число a (1 ≤ a ≤ 100000) - кількість води, влите у два гіфа. Наступні два рядки описують два гіфа P та Q відповідно. Кожен гіф задається у вигляді k x_1 y_1 x_2 y_2 ... x_k y_k, де k - кількість точок у гіфі (n для P та m для Q), послідовність x_i y_i задає координати точок гіфа.
Вивести t рядків, кожен з яких містить одне число L - кінцевий рівень води, виражений в одиницях y координат, округлений до трьох десяткових знаків.