Соединенные гифы
Гифы (множественное слово от гиф) - это объекты, подобные воронкам. Определим гиф как двумерный объект, заданный последовательностью точек (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 координат, округленный до трех десятичных знаков.