Cerința

În regatul Ofni este Ajunul Crăciunului. Maleficul vrăjitor Irum din regatul vecin Akizif a aruncat un blestem asupra a k orașe din regatul Ofni, orașe care pot fi vizualizate ca matrici cu n i linii și m i coloane. Acest blestem constă în grinchificarea persoanelor din aceste orașe. Blestemul funcționează în felul următor. Irum alege din fiecare oraș mai multe case (pătrățele unitate ale matricei oraș) și le infectează. După ce termină de infectat casele de pornire, blestemul infectează oricare casă cu cel puțin doi vecini pe linie sau coloană. Cum blestemul se mișcă foarte rapid, transformările se petrec instantaneu. Pentru că era bătrân și obosit, Irum a făcut o greșeală, astfel că dacă blestemul nu va putea infecta întregul oraș, acesta se destramă și nu va avea efect. Dacă toate casele din oraș vor fi afectate, toți locuitorii orașului vor deveni grinchi.

Pentru a salva Crăciunul, bunul vrăjitor Picm trebuie să găsească o vrajă pentru a preschimba locuitorii grinchificați ai orașului înapoi cum erau. Cu ajutorul unui spion, Picm a aflat câte orașe sunt infectate, dimensiunile acestora, precum și câte și care au fost celule infectate inițial de Irum. Picm știe că vraja se află în cartea lui magică, Pbofni, la pagina numărul P unde P este suma oki*ini*mi%97 și oki este 1 dacă orașul a fost infectat și 0 în cazul contrar. Cum în Ofni nu s-au inventat încă calculatoarele și apusul e aproape, Picm, bun algoritmician de altfel, vă cere ajutorul pentru a afla numărul paginii și a salva Crăciunul de pandemia de grinchi.

Problema are două cerințe.
Pentru c = 1, se cere determinarea numărului de orașe grinchificate.
Pentru c = 2, se cere numărul paginii P la care se află vraja salvatoare.

Date de intrare

Fișierul de intrare pandemica.in va conține pe prima linie, separate printr-un spațiu, valorile c și k, unde c numărul cerinței și k numărul de orașe blestemate. Pe următoarele linii vom avea de k ori următoarele: dimensiunile ni și mi ale orașelor și numărul xi de case infectate. Pe următoarele xi linii se află câte o pereche de numere marcând indicele liniei și coloanei unei celule infectate din orașul cu indicele i.

Date de ieșire

Dacă c = 1, fișierul de ieșire pandemica.out va conține o singură valoare egală cu numărul de orașe grinchificate (infectate complet). Dacă c = 2, fișierul de ieșire va conține o singură valoare marcând pagina la care se află vraja căutată de Picm.

Restricții și precizări

• 1 ≤ k ≤ 200
• 1 ≤ ni, mi≤ 500
• 10 puncte pentru cerința 1 cu 1 ≤ k ≤ 50
• 30 puncte pentru cerința 1 fără restricții suplimentare
• 10 puncte pentru cerința 2 cu ni, mi≤ 75
• 50 puncte pentru cerința 2 fără restricții suplimentare
• Succes :)

Exemplul 1

pandemica.in

1 3
5 5 10
2 2
2 3
3 2
4 2
1 1
1 4
2 5
4 5
5 1
5 4
4 4 5
1 2
2 2
3 2
2 1
2 3
5 5 4
2 2
3 2
2 3
3 3

pandemica.out

1

Exemplul 2

pandemica.in

2 3
5 5 10
2 2
2 3
3 2
4 2
1 1
1 4
2 5
4 5
5 1
5 4
4 4 5
1 2
2 2
3 2
2 1
2 3
5 5 4
2 2
3 2
2 3
3 3

pandemica.out

1

Explicație

Simulând modul în care se extinde infecția observăm că doar primul oraș este grinchificat complet. Astfel, pentru cerința 1, rezultatul este 1 (un singur oraș din cele 3), iar pentru cerința 2, numărul paginii este P=1*15*5%97+0*24*4%97+0*35*5%97=1+0+0=1.