WoW
Nyu-York Mərkəzi Parkının zooparkında "Wonders of Worlds" adlı ikiölçülü onlayn oyun çox populyardır. Bu oyun, vahid ölçüdə hüceyrələrə bölünmüş sonsuz bir səthdə keçirilir. Hər bir hüceyrə iki tam ədədlə, x və y koordinatları ilə təyin olunur. Oyunun ən maraqlı xüsusiyyətlərindən biri, ən yüksək səviyyəli (85) oyunçular üçün xüsusi turnir arenasında keçirilən döyüşlərdir. Arena, n×m ölçülü düzbucaqlı bir sahədir. Arenanın sol alt küncü (0, 0), sağ üst küncü isə (n-1, m-1) koordinatlarında yerləşir. Arenanın hər bir hüceyrəsində eyni anda yalnız bir oyunçu ola bilər. Oyunçular növbə ilə hərəkət edirlər. Bir hərəkət zamanı oyunçu ya rəqibə hücum edə bilər, ya da arenanın başqa bir sektoruna keçə bilər.
Bu gün Riko, ölüm mələyi rolunda, sehrbaz Şkiperi döyüşə çağırdı. WoW-da qaydaya görə, çağıran oyunçu ikinci hərəkət edir, yəni ilk hərəkəti Şkiper edəcək.
Döyüş başlamazdan əvvəl, Riko ilə eyni gildiyada olan Kovalyski, Şkiperi xəbərdar etdi ki, Riko oyun mühərrikində bir səhv tapıb və bu səhv ona rəqibini bir bacarıqla dərhal məğlub etməyə imkan verir. Şkiperin yeganə çıxış yolu Riko'ya hücum etməkdir.
WoW-da sehrbazların sehr sistemi unikal xüsusiyyətlərə malikdir. Hər bir sehrbazın k əsas sehrdən ibarət dəsti var. Hər bir əsas sehr i, tam koordinatlı d_i vektor dəsti ilə müəyyən edilir. Sehr söyləndikdə, müəyyən bir başlanğıc nöqtəsindən başlayaraq vektorlar ardıcıllığı ilə hərəkət edilir. Bütün hərəkətlər başa çatdıqda sehr partlayır və əgər rəqib həmin nöqtədədirsə, ona zərər vurur.
Sehrbazın əsas xüsusiyyəti, müxtəlif əsas sehrləri birləşdirə bilməsidir. Kombinasiya, bəzi əsas sehrlərin ardıcıl tətbiqindən ibarətdir. Birinci sehrin hərəkətləri bitdikdən sonra partlamır, ikinci sehr birincinin bitdiyi nöqtədən başlayır. İkinci sehrin hərəkətləri bitdikdən sonra üçüncü sehr tətbiq olunur və s. Kombinasiyadakı son sehrin hərəkətləri bitdikdən sonra partlayır.
Qeyd edək ki, döyüş arenaları keçilməz anti-sehrli baryerlərlə əhatə olunub. Əsas sehr yalnız hərəkətlər zamanı arenanın sərhədlərindən kənara çıxmadıqda tətbiq edilə bilər. Eyni qayda kombinasiyalara da aiddir.
Çünki mümkün kombinasiyaların sayı çoxdur, Şkiper sizdən Riko'ya zərər verə biləcək və ümumi sayı 10^6-dan çox olmayan əsas sehrlərin kombinasiyasını tapmaqda kömək etməyinizi xahiş edir, ya da bunun mümkün olmadığını müəyyən edin.
Zəmanət verilir ki, əgər məsələnin həlli varsa, o, 10^6-dan çox əsas sehrin birləşdirilməsini tələb etmir.
Giriş verilənləri
Girişin ilk sətirində üç tam ədəd n, m və k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 50) — arenanın ölçüləri və əsas sehrlərin sayı verilir. İkinci sətirdə tam ədədlər x_1, y_1, x_2, y_2 (1 ≤ i ≤ 2, 0 ≤ x_i ≤ n, 0 ≤ y_i ≤ m) (x_1, y_1) ≠ (x_2, y_2) — arenada Şkiper və Riko'nun koordinatları verilir. Sonra k sətirdə əsas sehrlərin təsviri gəlir. Girişin (i+2)-ci sətirində tam ədəd d_i (1 ≤ d_i ≤ 5·10^5) — əsas sehirdəki hərəkətlərin sayı verilir. Sonra d_i cüt tam ədəd x_j, y_j (1 ≤ j ≤ d_i, -n < x_j < n, -m < y_j < m) — hərəkətləri təyin edən vektorların koordinatları verilir. Bütün əsas sehrlərdəki vektorların ümumi sayı 5·10^5-i keçmir. Bütün ədədlər bir boşluqla ayrılır.
Çıxış verilənləri
Əgər məqsədə çatmaq üçün 10^6-dan çox olmayan əsas sehrlərin kombinasiyası varsa, çıxışın ilk sətirində p tam ədədini — tapılan kombinasiyadakı əsas sehrlərin sayını verin. İkinci sətirdə tətbiq ardıcıllığı ilə p ədədini, bir boşluqla ayrılmış şəkildə verin — əsas sehrlərin nömrələri. Əsas sehrlər girişdə təsvir edildiyi ardıcıllıqla birdən başlayaraq nömrələnir. Əgər bir neçə həll varsa, istənilən birini verin.
Əgər həll yoxdursa, ilk sətirdə -1 ədədini verin.