İşğal#5550
Keçmişdə ilk kosmik uçuşumuzdan bəri yüzlərlə əsr keçdi, lakin ən uzaq insan məskənləri heyrətamiz yeni dünyalar deyil, yalnız bir neçə paslanmış kosmik stansiya oldu. Biz heç vaxt hazırlıqsızlığımızı bilənləri dinləmədik və zaman keçdikcə inanılmaz bir şeyə inandıq: Yer fəth edildi. Planetimizin dövlətləri iki yad imperiya arasında bölünəcək, onlar bu razılaşmanı qəbul etdikdən sonra.
Bu gün Yer kürə formasındadır və səthi dövlətlərdən ibarətdir. Hər bir dövlət qapalı sərhədləri və əlaqəli daxili sahəsi olan bir ərazidir, sərhədlər öz-özünə kəsişmir. Bir nöqtədə üçdən çox dövlət sərhədi kəsişə bilməz. Dünyamızın bölünməsindən sonra hər bir imperiyanın ərazisi də qapalı sərhədlərə və əlaqəli daxili sahəyə malik olmalıdır, sərhədlər öz-özünə kəsişməməlidir.
Yadplanetlilər aşağıdakı problemlə qarşılaşacaqlar: planetimizin səthinin bölünməsini bilmək və hər bir imperiyanın ərazisindəki dövlətlərin sayının fərqinin mütləq dəyərini hesablayın. Onların etimadını qazanmaq üçün, bəşəriyyətin liderləri onlara kömək etməyə qərar verdilər.
Birinci sətir testlərin sayını t ehtiva edir. Daha sonra t testlər gəlir.
Hər bir test dünya xəritəsinin təsvirini ehtiva edir, ardınca yadplanetlilərin sorğuları gəlir.
Bir nöqtəni xüsusi adlandıraq, əgər orada üç sərhəd kəsişirsə. Dünya xəritəsinin təsviri olan ilk sətir n (4 ≤ n ≤ 100 000) dəyərini ehtiva edir, daha sonra n sətir gəlir, hər biri x_i, y_i, z_i, s_{i,1}, s_{i,2}, s_{i,3} (1 ≤ i ≤ n) ədədlərindən ibarətdir, xüsusi nöqtələri təsvir edir. Həqiqi ədədlər x_i, y_i, z_i - i-ci xüsusi nöqtənin koordinatlarıdır. Bütün xüsusi nöqtələr eyni mərkəzi (0, 0, 0) və radiusu r (1 ≤ r ≤ 1000) olan bir sferanın səthinə aiddir. Tam ədədlər s_{i,1}, s_{i,2}, s_{i,3} i-ci xüsusi nöqtə ilə sərhədləşən xüsusi nöqtələri göstərir. Sərhəd həmişə böyük dairənin kiçik qövsüdür. Sərhəd heç vaxt iki diametral əks nöqtəni birləşdirmir.
Dünya təsvirindən sonra sorğular gəlir. İlk sətir tam m (1 ≤ m ≤ 200 000) - sorğuların sayını ehtiva edir. Növbəti m sətirin hər biri iki imperiya arasında yer səthinin bölünməsini təsvir edir. i-ci bölünmənin təsviri tam k_i ədədi ilə başlayır, ardınca sərhədin keçdiyi xüsusi nöqtələrin identifikatorları gəlir. Başqa heç bir xüsusi nöqtə bölünmə sərhədində yerləşmir. Sərhəd yuxarıda qeyd olunan şərtlərə cavab verir.
Hər bir test üçün ayrı sətirdə m ədəd çıxarın. i-ci ədəd i-ci bölünməyə görə hər bir imperiyadakı dövlətlərin sayının fərqinin modulu olmalıdır.
Nümunə 1