joc

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 \cdot N$ celule, aşezate pe $N$ linii şi $N$ coloane; celulele pătratului sunt numerotate de la $1$ la $N^2$ 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 $N^2$ 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 (figura $1$), diagonala secundară sau una din cele două semidiagonale paralele şi alăturate acesteia (figura $2$);
• o rundă se încheie fără un câştigător dacă după marcarea celor $N^2$ celule nu există pe tabla de joc nicio linie, coloană, diagonală sau semidiagonală marcate cu acelaşi simbol.

Cerință

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 joc.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 joc.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 joc.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 \leq N \leq 100$;
• $1 \leq K \leq 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. Se acordă $10$ puncte din oficiu.

Exemplul 1

joc.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

joc.out

2 1

Explicație

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

Exemplul 2

joc.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

joc.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$.