WoW#2741
Nyu-Yorkun Central Park Zooparkında ikiölçülü "Wonders of Worlds" onlayn oyunu çox populyardır. Oyun sonsuz bir müstəvidə, vahid hüceyrələrə bölünmüş bir sahədə baş verir. Hər bir hüceyrə iki tam ədəd və ilə, yəni koordinatları ilə təyin olunur. Xüsusilə ən yüksək (85-ci) səviyyə oyunçuları üçün əsas xüsusiyyətlərdən biri xüsusi turnir arenasında keçirilən duellərdir. Arena n \times m ölçülü bir düzbucaqlıdır. Arenanın sol aşağı küncü , sağ yuxarı küncü isə (n-1, m-1) nöqtəsində yerləşir. Eyni zamanda hər hüceyrədə yalnız bir oyunçu ola bilər. Oyunçular növbə ilə hərəkət edirlər; növbəsində oyunçu rəqibinə hücum edə və ya arenada başqa bir hüceyrəyə keçə bilər.
Bu gün Rico, Ölüm Mələyi kimi oynayaraq, maq rolunda çıxış edən Skipper-ə meydan oxuyur. WoW qaydalarına görə, meydan oxuyan ikinci hərəkət edir, beləliklə ilk gedişi Skipper edir.
Döyüş başlamazdan əvvəl Rico-nun gildiya yoldaşı Kowalski Skipper-i xəbərdar edir ki, Rico oyun mühərrikində bir səhv tapıb və bu səhv ona bir zərbə ilə rəqibini dərhal məğlub etməyə imkan verir. Skipper-in yeganə şansı Rico-ya birinci hücum etməkdir.
WoW-da maqiya sistemi unikal işləyir: hər maqın əsas sehrdən ibarət dəsti var. Hər bir -ci əsas sehr tam ədədlərlə ifadə olunan d_i vektordan ibarət bir ardıcıllıqdır. Sehr istifadə olunanda, o, müəyyən bir nöqtədən başlayır və növbə ilə həmin vektorlara uyğun hərəkət edir. Bütün hərəkətlər başa çatdıqdan sonra sehr partlayır və əgər qarşı tərəf həmin nöqtədədirsə, ona zərər dəyir.
Maq əsas sehrləri birləşdirə bilər, yəni bir neçə sehr bir-birinin ardınca tətbiq oluna bilər. Növbəti sehr əvvəlkinin bitdiyi nöqtədən başlayır və yalnız bütün sehrlər ardıcıllığı başa çatdıqdan sonra sehr partlayır.
Döyüş arenası keçilməz anti-maqiya baryeri ilə əhatə olunub. Əsas sehr yalnız hərəkətlərin heç biri arena sərhədlərini aşmırsa, tətbiq oluna bilər. Eyni qayda sehrlərin birləşməsinə də aiddir.
Çünki mümkün sehr birləşmələrinin sayı çox böyükdür, Skipper səndən istəyir ki, ard-arda ən çox 10^6 əsas sehrdən ibarət elə bir kombinasiyanı tapasan ki, onu tətbiq etmək mümkün olsun və Rico-ya zərər vursun, yaxud bunun mümkün olmadığını müəyyən edəsən.
Zəmanət verilir ki, əgər həll varsa, kombinasiya üçün 10^6-dan çox sehr tələb olunmur.
Birinci sətirdə , və (1 \leq n, m \leq 1000, 1 \leq k \leq 50) — arenanın ölçüləri və əsas sehrlərin sayı verilir. İkinci sətirdə x_1, y_1, x_2, y_2 (0 \leq x_i \leq n, 0 \leq y_i \leq m, (x_1, y_1) \neq (x_2, y_2)) — Skipper və Rico-nun koordinatları verilir. Sonra blokda sehrlər təsvir olunur. (i+2)-ci sətirdə d_i (1 \leq d_i \leq 5 \cdot 10^5) — -ci əsas sehrdə hərəkətlərin sayı, ardınca d_i cüt tam ədəd x_j, y_j (-n < x_j < n, -m < y_j < m), yəni hərəkətləri təyin edən vektorlar verilir. Bütün sehrlər üzrə vektorların ümumi sayı 5 \cdot 10^5-dən artıq deyil. Bütün ədədlər bir boşluqla ayrılıb.
Əgər məqsədə çatmaq üçün ard-arda ən çox 10^6 əsas sehr tətbiq etməklə həll tapmaq mümkündürsə, birinci sətirdə — istifadə olunan sehrlərin sayı, ikinci sətirdə isə boşluqla ayrılmış ardıcıllıqla həmin sehrlərin nömrələrini (sehrlər daxil olduqları sıradan 1-dən başlayaraq nömrələnir) yazın. Bir neçə həll mümkündürsə, istənilənini verə bilərsiniz.
Əgər mümkün deyilsə, birinci sətirdə çıxış verin.
Nümunə 1