Dəhliz
Muzey hazırda bağlanır və sizin baxa biləcəyiniz yalnız bir dəhliz var. Vaxt məhdudiyyətinə baxmayaraq, bu fürsəti qaçırmamağa qərar verdiniz.
Dəhlizdə heç bir eksponat yoxdur - dəhlizin özü eksponatdır. Üst tərəfdən baxıldığında, iki əks divar görünür, hər biri çoxbucaqlı zəncir təşkil edir (çoxbucaqlı zəncir - zirvələrin seqmentlərlə birləşdirildiyi ardıcıllıqdır). Dəhlizin planına baxdıqda, hər bir zəncirdə x koordinatlarının (sıx) artan qaydada olduğunu görmək olar. Üstəlik, bu qaydada ilk və son zirvələr iki divarın üst-üstə düşdüyü yeganə nöqtələrdir - bu, giriş və çıxışın yerləşdiyi yerdir.
Mühafizəçilərdən qaçmaq üçün, bir müddət sonra sizi təqib edəcəklər, girişdən çıxışa ən qısa yolu hesablamaq lazımdır.
Giriş verilənləri
Birinci sətir testlərin sayını T ehtiva edir. Sonra isə T testlər gəlir.
Hər testin birinci sətiri yuxarı çoxbucaqlı zəncirdəki zirvələrin sayını n_1 ehtiva edir. Sonrakı n_1 sətirin hər biri iki tam ədəd x_i, y_i (|x_i|, |y_i| ≤ 10^9) - zəncirin i-ci zirvəsinin koordinatlarını ehtiva edir. Zirvələr x koordinatının artan qaydasında sıralanır. Yuxarı zəncirin təsvirindən sonra n_2 dəyəri olan bir sətir gəlir, sonra isə aşağı zəncirin təsviri gəlir. n_1 + n_2 ≤ 200 000 olduğunu qəbul etmək olar. Yuxarı divarın bütün uzunluğu boyunca aşağı divardan yuxarıda olduğu təmin edilir, istisna olaraq sonlar.
Çıxış verilənləri
Hər test üçün zəncirlərin sonlarını birləşdirən və iki çoxbucaqlı zəncir arasında yerləşən ən qısa yolun uzunluğunu çıxış edin. Çıxış 3 onluq dəqiqliyi ilə olmalıdır.