시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 2 2 50.000%

문제

Pan Michał chce wykopać nową studnię. Dysponuje planem terenu swojej działki, na którym przedstawione są dwa zarysy: powierzchni gruntu oraz początku warstwy wodonośnej, które mają kształt linii łamanych. Pan Michał wynajął już specjalne wiertło, które może wiercić jedynie w pionie. Koszty wiercenia są całkiem spore, nic dziwnego więc, że zastanawia się, na jaką głębokość co najmniej musi wykonać odwiert, by dotrzeć z powierzchni do warstwy wodonośnej.

입력

W pierwszej linii znajduje się jedna liczba naturalna Z ( 1 <= Z <= 5 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii znajduje się jedna liczba naturalna ( 2 <= n <= 100 000 ), oznaczająca liczbę punktów łamanej opisującej powierzchnię gruntu na działce pana Michała. W drugim wierszu występuje n par liczb naturalnych xiyi ( 1 <= xiyi <= 109 ), pooddzielanych pojedynczymi odstępami. Dla każdego 1 <= zachodzi: xi xi+1.

W kolejnych dwóch liniach znajduje się analogiczny opis łamanej opisującej początek warstwy wodonośnej pod działką pana Michała. W pierwszej z nich znajduje się liczba naturalna ( 2 <= < n+m <= 100 000 ), oznaczająca liczbę punktów, a w drugiej z linii jest m par liczb naturalnych uivi ( 1 <= uivi <= 109 ), pooddzielanych pojedynczymi odstępami. Dla każdego 1 <= zachodzi: ui ui+1.

Warstwa wodonośna znajduje się w całości pod powierzchnią gruntu ( te dwie łamane nie mają punktów wspólnych ). Ponadto zachodzą równości: x1 = u1 oraz xn = um.

출력

Dla każdego zestawu testowego w osobnej linii należy wypisać jedną liczbę rzeczywistą dodatnią - minimalną głębokość dzielącą powierzchnię od warstwy wodonośnej. Wartość tę należy zaokrąglić do dokładnie dwóch miejsc po przecinku.

예제 입력 1

3
2
1 2 5 6
2
1 1 5 5
2
1 10 10 10
3
1 5 5 8 10 5
2
1 10 10 10
3
1 5 5 2 10 6

예제 출력 1

1.00
2.00
4.00

힌트

W pierwszym teście na całej długości działki szukana różnica głębokości wynosi 1.

W drugim teście różnica jest najmniejsza w punkcie x = 5, i jest tam równa dokładnie 2.

W trzecim teście różnica jest najmniejsza w punkcie x = 10.