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 ≤ 10
• 1 ≤ 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.