Birləşmiş qıflar
Qıflar çalaya bənzər obyektlərdir. Qıfı (p_1, p_2, ..., p_n) nöqtələr ardıcıllığı ilə verilmiş və aşağıdakı şərtləri ödəyən ikiölçülü obyekt kimi təyin edək:
3 ≤ n ≤ 1000;
Tutaq ki, p_i nöqtəsi (x_i, y_i) koordinatlarına malikdir. Əgər elə c (1 < c < n) indeksi varsa ki, y_1 > y_2 > ... > y_c və y_c < y_c_{+1} < y_c_{+2 }< ... < y_n, onda p_c nöqtəsi qıfın çıxıntı nöqtəsi adlanır.
Bütün 1 ≤ i < c üçün x_i < x_c və bütün c < i ≤ n üçün x_i > x_c;
1 < i < c üçün p_i_{-1}_{ }nöqtəsinin p_i ətrafında saat əqrəbinin hərəkəti istiqamətində fırlatması nəticəsində p_i_{-1} nöqtəsinin p_{i }və p_i_{+1} ilə kollinear olması üçün zəruri olan bucaq 180 dərəcədən böyükdür. Analoji olaraq, c < i < n üçün p_i_{-1} nöqtəsinin p_i ətrafında saat əqrəbinin hərəkəti istiqamətində fırlanması zamanı p_{i }və p_i_{+1} ilə kollinear olması üçün zəruri olan bucaq da 180 dərəcədən böyükdür.
İki qonşu nöqtəni birləşdirən parçalar yalnız öz uc nöqtələrində kəsişirlər.
Məsələn, aşağıdakı şəkildə altı nöqtəli və c = 4 olan halda qıf təsvir edilmişdir:
(p_1p_2, p_2p_3, ..., p_n_{-1}p_n) parçalar ardıcıllığını qıfın gövdəsi adlandıracağıq. Sizə iki P = (p_1, p_2, ..., p_n) və Q = (q_1, q_2, ..., q_m) qıfları verilmişdir. Burada p_i nöqtələrinin bütün x koordinatları mənfi tam ədədlərdir, q_i nöqtələrinin bütün x koordinatları isə müsbət tam ədədlərdir. İki qıfın çıxıntılarının bir-biri ilə nazik borucuq ilə birləşdirildiyini nəzərə alaraq, qıfları su ilə dolduraq. Su qəbul edilməyə başladıqda qıflar məlum fiziki qanuna uyğun olaraq dolmağa başlayacaq (hər iki qıfda suyun səviyyəsi eyni olacaq). Əgər P qıfında suyun səviyyəsi min(y_1, y_n) çatacaqsa, onda su qıfdan daşıb tökülməyə başlayacaq (eyni sözləri Q qıfı haqqında da demək olar). Sizin proqram müəyyən miqdarda su töküldükdən sonra iki qıfdakı suyun səviyyəsini müəyyənləşdirməlidir. Məsələyə ikiölçülü fəzada baxdığımızdan suyun miqdarı dolmuş sahə ilə ölçüləcək. Qıfların çıxıntısını birləşdirən borucuqların həcmini sıfıra bərabər hesab edin.
Giriş verilənləri
Birinci sətirdə testlərin t sayı yerləşir. Hər bir test üç sətirdə verilir. Birinci sətirdə iki qıfa tökülmüş suyun miqdarı olan bir tam a (1 ≤ a ≤ 100000) ədədi yerləşir. Sonrakı iki sətir uyğun olaraq P və Q qıflarını təsvir edir. Hər bir qıf k sayda x_1 y_1 x_2 y_2 ... x_k y_k ədədləri şəklində təsvir edilir. Burada k – qıfdakı nöqtələrin sayı (P üçün n, Q üçün m), x_i y_{i }ardıcıllığı ilə qıfların nöqtələrinin koordinatları verilir.
Çıxış verilənləri
Çıxışa t sətir verilir. Onların hər birində suyun son səviyyəsini bildirən L ədədi koordinat vahidlərilə ifadə olunub və üç onluq işarəyədək yuvarlaqlaşdırılıb.