rebus

Revista REBUSICĂ a publicat un nou tip de rebus. Careul are $n$ linii şi $m$ coloane şi conţine $n \cdot m$ pătrăţele albe şi negre. Un cuvânt are cel puţin două litere şi se poate forma doar în pătrăţelele albe consecutive, pe orizontală sau verticală, fiecare pătrăţel alb conţinând o literă a cuvântului. Pentru că dimensiunea careului poate fi foarte mare, redactorul şef a hotărât ca definiţiile pentru cuvintele de pe orizontală şi cele pentru cuvintele de pe verticală să fie publicate în două ediţii succesive ale revistei.

Cerinţă

Scrieţi un program care, pentru un careu de dimensiuni date, cu poziţiile pătrăţelelor negre precizate, determină numerele de cuvinte ce vor fi completate pe orizontală şi pe pe verticală.

Date de intrare

Fişierul rebus.in conţine pe prima linie, separate printr-un spaţiu, dimensiunile careului: $n$, numărul de linii şi $m$ numărul de coloane. Următoarele $n$ linii conţin, separate prin câte un spaţiu, numărul de pătrăţele negre de pe linie apoi, în ordine strict crescătoare, coloanele pe care care se găsesc acestea.

Date de ieşire

Fişierul rebus.out conţine pe prima linie, separate prin câte un spaţiu, numărul de cuvinte ce se pot forma pe orizontală şi numărul de cuvinte ce se pot forma pe verticală.

Restricții și precizări

• $2 < n,m \leq 500$
• În careu sunt cel mult $10 \ 000$ de pătrăţele negre.
• Pentru fiecare număr de cuvinte corect calculat se acordă $50\%$ din punctajul pe test.

Exemplu

rebus.in

10 8
0
0
1 5
4 2 4 6 8
2 4 7
0
3 3 4 6
0
1 7
0

rebus.out

12 16

Explicație