Cerința

Dom’ Profesor Unu și Dom’ Profesor Doi au găsit o matrice cu n linii numerotate de la 1 la n și n coloane numerotate de la 1 la n și elemente numere naturale. Semnificativ marcați de algoritmul de determinare a celui mai lung subșir crescător, au inventat pe loc un joc:

• liniile cu indice impar aparțin lui Dom’ Profesor Unu, cele cu indice par aparțin lui Dom’ Profesor Doi;
• pentru fiecare linie a sa, Dom’ Profesor Unu determină lungimea maximă a unui subșir crescător;
• pentru fiecare linie a sa, Dom’ Profesor Doi determină lungimea maximă a unui subșir descrescător;
• scorul fiecărei linii este lungimea determinată;
• scorul total al fiecărui Dom’ Profesor este egal cu suma scorurilor liniilor corespunzătoare;
• jocul este câștigat de Dom’ Profesor cu scorul total mai mare.

Determinați scorului fiecărui Dom’ Profesor și stabiliți câștigătorul.

Date de intrare

Fișierul de intrare joc6.in conține pe prima linie numărul n; fiecare dintre următoarele n linii conține n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire joc6.out va conține pe prima linie două numere S1 S2, separate prin exact un spațiu, unde S1 este scorul lui Dom’ Profesor Unu, iar S2 este scorul lui Dom’ Profesor Doi. Linia a doua va conține unul dintre cuvintele:

• UNU – dacă câștigă Dom’ Profesor Unu;
• DOI – dacă câștigă Dom’ Profesor Doi;
• REMIZA – dacă scorurile sunt egale.

Restricții și precizări

• 1 ≤ n ≤ 150
• elementele matricei vor fi mai mici decât 1.000.000.000

Exemplu:

joc6.in

4
1 4 2 3
2 9 8 7
3 6 3 8
1 2 3 3

joc6.out

6 5
UNU

Explicație

• linia 1 este a lui Dom’ Profesor Unu. Scorul este 3 – subșirul 1 2 3;
• linia 2 este a lui Dom’ Profesor Dou. Scorul este 3 – subșirul 9 8 7;
• linia 3 este a lui Dom’ Profesor Unu. Scorul este 3 – subșirul 3 3 8;
• linia 4 este a lui Dom’ Profesor Doi. Scorul este 2 – subșirul 3 3.

Așadar, scorul total a lui Dom’ Profesor Unu este 3+3=6, iar scorul total al lui Dom’ Profesor Doi este 2+3=5. Câștigă Unu.