Gigi are un palat de T etaje, destul de monoton ca design. Fiecare etaj contine o retea de N x M camere patrate, cate M pe fiecare din cele N linii (numerotate de la 1). Fiecare camera contine un bec care initial poate fi aprins sau nu. Cu ocazia sarbatorilor pascale, Gigi vrea sa aprinda toate becurile din palatul sau folosindu-se de o aplicatie unde poate schimba starea becurilor pentru fiecare camera (din inchis in deschis si viceversa), pe ecran putand vizualiza toate camerele de pe un singur etaj. Din pacate, cand Gigi efectueaza o mutare si vrea sa apese in dreptul unei camere, el va apasa si in dreptul camerelor adiacente (de sus si jos, respectiv la stanga si dreapta, daca camerele exista, dar nu si pe diagoanala).
Nestiind cum poate proceda, el va cere ajutorul vostru si promite ca o sa va rasplateasca cu produse lactate. Gigi apreciaza modurile diferite de rezolvare a problemei, dar nu apreciaza redundanta. O secventa de mutari X ce aprinde toate becurile este considerata valida daca si numai daca nu exista alta secventa Y ce aprinde si ea becurile, cu Y ⊂ X.
Deoarece Gigi banuieste ca se va mai afla in aceasta situatie, aflati numarul de variante posibile de a face lumina pe fiecare etaj din palat si sa se afiseze o modalitate valida de a ilumina fiecare etaj (daca este posibil).
Date de intrare
Pe prima linie se citesc numerele N, M, T. Apoi, pentru fiecare etaj, se citesc pe urmatoarele N linii starea initiala a becurilor, cate M pe fiecare linie (1 - aprins, 0 - stins).
Date de iesire
Pe prima linie se va afisa numarul total de moduri. Daca nu exista nicio modalitate valida se va afisa doar 0. Altefel, pe urmatoarele linii se va afisa o modalitate valida de a aprinde toate becurile, pe a doua linie afisandu-se numarul de mutari. Apoi, pe fiecare linie se vor afisa mutarile a b cu semnificatia ca se efectueaza o apasare pe linia a si coloana b.
Restrictii
1 ≤ T ≤ 101 ≤ N, M ≤ 500 000- Se acorda
30%de punctaj pentru numarul de moduri. Atentie, acest numar trebuie printat neaparat, chiar daca este gresit. - Restul de
70%din punctaj pentru o solutie care respecta cerinta (daca aceasta exista).
Subtask 1 (40 puncte)
N · M ≤ 350
Subtask 2 (30 puncte)
N · M ≤ 1 000
Subtask 3 (10 puncte)
N · M ≤ 1 500
Subtask 4 (20 puncte)
N · M ≤ 500 000- Atentie
N, M ≥ 1
Exemplu
stdin
3 5 1
10110
01101
10010
stdout
8
5
2 2
1 4
2 3
1 5
2 5
stdin
4 4 2
1000
0000
0000
0000
0000
0000
0000
0000
stdout
0
16
10
2 1
2 2
2 3
2 4
3 1
3 4
4 1
4 2
4 3
4 4
Explicatii
Pentru al doilea exemplu: se poate demonstra ca nu exista nicio modalitate de a ilumina etajul cu becurile in configuratia
1000
0000
0000
0000
In schimb, exista 16 moduri de a aprinde toate becurile daca niciunul nu este initial aprins.