Xəzinəni Tap
Dörd yüz il əvvəl, bir qrup quldur bir arxipelaqda yerləşən adalardan birində xəzinə gizlədib. Təəssüf ki, bu quldurlar naviqasiya və kartoqrafiya sahəsində çox da bacarıqlı deyildilər. Buna görə də, xəritə əvəzinə, xəzinə adasındakı dağın zirvəsindən görünüşlərin rəsmlərini çəkdilər. Hər bir görünüş, xəzinə adasından görünə bilən arxipelagdakı digər iki və ya daha çox adanı soldan sağa doğru göstərir. Görünüşlər həmçinin çoxlu dumanla doludur, belə ki, rəsmdə görünən adaların arasında görünüş sahəsində olmalı olan bəzi adaları göstərməyə bilər. Məsələn, aşağıdakı Şəkil 1-də, əgər xəzinə Rummet-də gizlədilibsə, quldurlar soldan sağa doğru Wisket, Ginnet və Vinnet göstərən bir görünüş və ya soldan sağa doğru Liquorel və Cidrel göstərən bir görünüş çəkə bilərdilər. Quldurların 180 dərəcə baxış bucağı ilə iti görmə qabiliyyətinə sahib olduqları məlumdur, lakin pis rəsm bacarıqları var idi: onların rəsmlərində Wisket, Ginnet və Vinnet arasındakı məsafələr mənasızdır və Liquorel Cidrel-dən çox sola çəkilə bilərdi, halbuki əslində Rummet-dən görünüşdə Liquorel Cidrel-dən yalnız bir az sola olmalı idi, hətta onun bir hissəsini örtürdü. Xoşbəxtlikdən, rəsmlərdəki bütün adalar hər adanın üstündəki unikal qüllələr sayəsində asanlıqla müəyyən edilə bilər.
![](https://static.e-olymp.com/content/51/51f1d4058a791f2fcbf62c744c79b512d4cd00b6.jpg)
Şəkil 1. Hipotetik arxipelaqın xəritəsi və quldurların çəkə biləcəyi Rummet-dən bəzi görünüşlər.
İndi, dörd yüz il sonra, sizdə quldurların rəsmləri və bütün adaları göstərən əla, dəqiq bir arxipelaq xəritəsi var. Xəzinə hansı adada gizlədilib?
Giriş verilənləri
Girişin ilk sətri bir ədəd ehtiva edir: ardınca gələn arxipelaqların sayı. Hər bir arxipelaq aşağıdakı formata malikdir:
Bir sətrdə bir tam ədəd n, 1 ≤ n ≤ 125,000 şərtini ödəyir: arxipelaqdakı adaların sayı.
n sətir, hər biri iki tam ədəd x_i və y_i, 0 < x_i < 2^29 və 0 < y_i < 2^29 şərtini ödəyir: hər adadakı T_i qülləsinin koordinatları.
Bir sətrdə bir tam ədəd k: bu arxipelaq üçün test hallarının sayı. Hər bir test halı aşağıdakı formata malikdir:
Bir sətrdə bir tam ədəd m, 0 ≤ m ≤ 10,000 şərtini ödəyir: quldurların rəsmlərində görünən adaların cütlərinin sayı.
m sətir, hər biri iki tam ədəd l və r belə ki, 1 ≤ l ≤ n, 1 ≤ r ≤ n, l ≠ r, yəni T_l qülləsi T_r qülləsinin solunda çəkilib.
Çıxış
Girişdəki hər bir test halı üçün çıxış aşağıdakıları ehtiva etməlidir:
Hər bir xəzinə adası ola biləcək ada üçün arxipelaqdakı i-ci adanı müəyyən edən bir tam ədəd i (1 ≤ i ≤ n) olan bir sətir. Bu sətirlər artan sırada olmalıdır.
Bir sətir, ədəd 0 ehtiva edir.
Nümunə
Aşağıdakı giriş bir test halı olan bir arxipelaqı təsvir edir, yəni xəritəyə və Şəkil 1-də göstərilən görünüşlərə uyğun məlumatlar. Potensial xəzinə adaları Rummet, Alet və Schnahpsum-dur.