Təhlükəsiz əmanət
Seyf LTD. - yüksək keyfiyyətli seyflər istehsal edən bir şirkətdir. Onun son ixtirası, bir neçə güzgü ilə düzbucaqlı şəbəkə boyunca keçən lazer şüasından istifadə edən optik bağlama mexanizmidir.
Lazer aktivləşdirildikdə, şüa üfüqi olaraq yuxarı sıranın sol tərəfindən şəbəkəyə daxil olur. Şüa düşdüyü hər bir güzgüdən əks olunur. Hər bir güzgü diaqonal istiqamətdə 45 dərəcə bucaq altında, ya / ya da \ yerləşdirilmişdir. Əgər şüa sağ tərəfdən şəbəkənin aşağı sırasından çıxırsa, detektor tərəfindən aşkar edilir və seyf açılır (yuxarıdakı sol şəkilə baxın). Əks halda, seyf bağlı qalır və həyəcan siqnalı səslənir.
Hər bir seyfdə lazer şüasının şəbəkədən uğurla keçməsinin qarşısını alan bir güzgü yoxdur (yuxarıdakı sağ şəkilə baxın). Seyf, istifadəçiyə şəbəkənin boş hüceyrəsinə bir güzgü yerləşdirməyə imkan verən bir mexanizmə malikdir. Qanuni istifadəçi itkin güzgünün düzgün yerləşdirilməsini və istiqamətini bilir (/ yuxarıdakı şəkildə 4-cü sırada və 3-cü sütunda) və seyfi aça bilər. Bu məlumatı bilmədən, istifadəçi güzgünün yerləşdirilməsini və istiqamətini təxmin etməli olacaq ki, bu da böyük şəbəkələr üçün çətin bir vəzifə ola bilər.
Sizdən tələb olunur ki, verilmiş seyfin həqiqətən təhlükəsiz olub-olmadığını müəyyən edəsiniz. Təhlükəsiz seyfi əlavə güzgü yerləşdirmədən açmaq mümkün deyil, onun yeri və istiqaməti qeyri-müəyyən şəkildə müəyyən edilə bilər. Həqiqətən, lazım olan yerlər və istiqamətlər bir neçə ola bilər.
Giriş verilənləri
Hər bir test bir seyfi təsvir edir və dörd tam ədəd r, c, m və n (1 ≤ r, c ≤ 1000000 və 0 ≤ m, n ≤ 200000) olan bir sətirlə başlayır. Şəbəkə mexanizmi r sıra və c sütundan ibarətdir. Növbəti m sətirin hər biri iki tam ədəd r_i və c_i (1 ≤ r_i ≤ r və 1 ≤ c_i ≤ c) ehtiva edir ki, bu da / güzgüsünü r_i sırada və c_i sütununda təyin edir. Növbəti n sətirlər eyni üsulla \ güzgülərin yerini təyin edir. Bütün m + n güzgü mövqeləri cüt-cüt fərqlidir.
Çıxış verilənləri
Hər bir test üçün onun nömrəsini və aşağıdakı məlumatı çıxarın:
Əgər güzgü yerləşdirmədən seyf açılırsa, 0.
Əgər güzgü yerləşdirmədən seyfi açmaq mümkün deyilsə, lakin onu açmaq üçün dəqiq k mövqe varsa, və (r, c) - leksikoqrafik olaraq ən kiçik (sıra, sütun) mövqedirsə, k r c. Hər iki güzgü mövqeyinin - həm / həm də \ seyfi açdığı mövqe bir hesab edilir.
Əgər seyfi nə güzgü yerləşdirmədən, nə də güzgü yerləşdirməklə açmaq mümkün deyilsə, impossible.