Inspirați de clasicul joc Tic-Tac-Toe (X și 0), Teodora și Ștefan își propun să joace ceva asemănător, adăugând jocului clasic câteva reguli noi:

• tabla de joc este un pătrat de latură N, care este împărțit în N*N celule, așezate pe N linii și N coloane; celulele pătratului sunt numerotate de la 1 la N2 parcurgând liniile de sus în jos, și coloanele de la stânga la dreapta;
• Teodora va marca celulele cu X (litera X), iar Ștefan cu 0 (cifra 0);
• în cadrul unei runde, copiii marchează alternativ câte o celulă din pătrat, nemarcată anterior;
• o rundă a jocului este descrisă printr-un șir format din exact N2 numere naturale reprezentând celulele pătratului, în ordinea în care au fost marcate succesiv de cei doi copii;
• jocul are K runde; prima este începută de Teodora, a doua de Ștefan, a treia Teodora, a patra Ștefan și așa mai departe;
• o rundă este câștigată de jucătorul care reușește primul să marcheze complet o linie, o coloană, diagonala principală sau una din cele două semidiagonale paralele și alăturate cu aceasta, diagonala secundară sau una din cele două semidiagonale paralele și alăturate acesteia;
• o rundă se încheie fără un câștigător dacă după marcarea celor N2 celule nu există pe tabla de joc nicio linie, coloană, diagonală sau semidiagonală marcate cu același simbol.

Cerințe

Cunoscând numerele N, K și cele K șiruri de numere care reprezintă rundele jucate, scrieți un program care să rezolve una dintre următoarele două cerințe:

1. Să se determine câte runde a câștigat fiecare copil.
2. Să se determine care este cel mai mare număr de marcări efectuate până la câștigarea unei runde.

Date de intrare

Fișierul de intrare joc7.in conține pe prima linie un număr natural C. Pentru toate testele, C poate lua numai valorile 1 sau 2. Pe a doua linie se află două numere naturale N și K, separate prin câte un spațiu, reprezentând dimensiunea tablei de joc și respectiv numărul de runde jucate. Pe următoarele K linii sunt descrise rundele de joc, câte o rundă pe câte o linie a fișierului. În cadrul liniilor, numerele sunt separate prin câte un spațiu.

Date de ieșire

Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fișierul de ieșire joc7.out va conține pe prima linie două numere naturale t și s, separate printr-un spațiu, unde t reprezintă numărul de runde câștigate de Teodora, iar s numărul rundelor câștigate de Ștefan.

Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fișierul de ieșire joc7.out va conține pe prima linie numărul cel mai mare de marcări efectuate până la câștigarea unei runde.

Restricții și precizări

• 3 ≤ N ≤ 100
• 1 ≤ K ≤ 25
• La fiecare joc se câștigă cel puțin o rundă.
• Pentru rezolvarea corectă a primei cerințe se acordă 45 de puncte, iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 45 de puncte. În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

joc7.in

1
4 4
16 13 15 9 10 1 5 2 6 14 3 7 11 4 8 12
1 2 3 4 5 6 7 8 12 11 10 9 13 14 15 16
1 5 9 6 2 7 3 8 4 10 11 12 13 14 15 16
1 2 3 4 8 7 6 5 12 11 10 9 16 15 14 13

joc7.out

2 1

Explicație

Ilustrarea rundelor de joc până la momentul identificării unui câștigător este următoarea:

• Runda 1 (începe Teodora): Runda este câștigată de Teodora după 7 marcări. Se completează semidiagonala situată sub diagonala principală.
• Runda 2 (începe Ştefan): Runda este câştigată de Teodora după 14 marcări. Se completează semidiagonala situată sub diagonala secundară.
• Runda 3 (începe Teodora): Runda este câştigată de Ștefan după 8 marcări. Se completează linia a doua.
• Runda 4 (începe Ştefan): Runda nu este câştigată de niciun jucător.

Exemplul 2

joc7.in

2
4 4
16 13 15 9 10 1 5 2 6 14 3 7 11 4 8 12
1 2 3 4 5 6 7 8 12 11 10 9 13 14 15 16
1 5 9 6 2 7 3 8 4 10 11 12 13 14 15 16
1 2 3 4 8 7 6 5 12 11 10 9 16 15 14 13

joc7.out

14

Explicație

Doar 3 dintre cele 4 runde jucate au fost câştigate. Până în momentul câştigării în prima rundă s-au făcut 7 marcări, în a doua 14, iar în a treia 8. Deci numărul maxim de marcări făcute până la câştigarea unei runde este 14.