Алтыbucaqlı çubuqlar
Rəqəmsiz altıbucaqlı şəbəkəni nəzərdən keçirək. Şəbəkə, eyni ölçülü düzgün altıbucaqlı hüceyrələrdən ibarətdir və aşağıda göstərildiyi kimi yerləşdirilmişdir. Şəkildə, hər bir hüceyrəni müəyyən etmək üçün istifadə olunan koordinat sistemi də göstərilmişdir. Şəbəkənin hər bir hüceyrəsi ya boş, ya da bloklanmış ola bilər.
Şəkil: Şəbəkənin bir hissəsi
Şəbəkəyə təsadüfi şəkildə bir neçə çubuq yerləşdirilmişdir. Hər bir çubuğun uzunluğu bir "altıbucaqlı vahidinə" bərabərdir. Bu, çubuğun uclarının qonşu hüceyrələrin mərkəzlərində yerləşdiyini göstərir. Sizin vəzifəniz çubuqları elə hərəkət etdirməkdir ki, qapalı düzgün altıbucaqlı əldə edəsiniz.
Aşağıdakı şəkillərdə çubuqlardan hazırlanmış qapalı altıbucaqlıların nümunələri verilmişdir.
Sizə şəbəkədə yerləşdirilmiş çubuqların başlanğıc koordinatları verilir. Həmçinin bloklanmış hüceyrələrin koordinatları da təqdim olunacaq. Bir gedişdə aşağıdakı əməliyyatlardan birini həyata keçirə bilərsiniz:
Bir çubuq seçin və onu atın.
Bir çubuq seçin və onu uclarından birinin ətrafında 60 dərəcə saat əqrəbi istiqamətində və ya əksinə döndərin.
Bir çubuq seçin və onu çubuq uzunluğunda itələyin.
Çubuqlar heç vaxt bloklanmış hüceyrələri tutmamalıdır. Lakin iki çubuq eyni hüceyrəni eyni anda tuta bilər.
Yuxarıdakı şəbəkə vəziyyətini nəzərdən keçirək. Maneə (1, 1) koordinatlı hüceyrədə yerləşir və çubuqların ucları (0, 0) - (1, 0) hüceyrələrindədir. Çubuq üzərində dörd mümkün əməliyyat aşağıda verilmişdir.
Bütün əməliyyatlar başa çatdıqda, şəbəkədə çubuqlar ətrafında yatmadan qapalı düzgün altıbucaqlı yaranmalıdır. Bu o deməkdir ki, şəbəkədə dəqiq 6*x çubuq var, burada x - təbii ədəddir. Bunu ən az əməliyyat sayında edə bilərsinizmi?
Giriş verilənləri
Birinci sətir testlərin sayını T (T < 50) ehtiva edir. Hər bir test mövcud çubuqların sayından S (S < 9) başlayır. Növbəti S sətirlər çubuqların koordinatlarını x_1 y_1 x_2 y_2 formatında təsvir edir, bu da (x_1, y_1)-dən (x_2, y_2)-yə qədər çubuğu göstərir. Koordinatlar düzgündür və hər bir çubuğun uzunluğu yuxarıda göstərildiyi kimi altıbucaqlı vahidinə bərabərdir. Növbəti sətirdə maneələrin sayı B ( B < 20) verilir. Növbəti B sətirlər hər bir maneənin koordinatlarını verir. Koordinatlar x_1 y_1 formatındadır. Zəmanət verilir ki, maneələr heç bir çubuqla kəsişmir. Bütün koordinatlar (çubuqlar və maneələr) [-4, 4] intervalında yerləşir.
Qeyd: Unutmayın ki, biz sonsuz şəbəkə ilə işləyirik. Buna görə də cavabda çubuqların koordinatları [-4, 4] intervalından kənarda ola bilər.
Çıxış verilənləri
Hər bir test üçün onun nömrəsini və ardınca lazım olan ən az əməliyyat sayını çıxarın. Əgər çubuqlardan altıbucaqlı yaratmaq mümkün deyilsə, "impossible" çıxarın. Giriş və çıxış formatına riayət edin.