boats

Pe o foaie de matematică cu $N$ pătrățele orizontale (pe aceeași linie) și $M$ pătrățele verticale (pe aceeași coloană), Alex a pictat nave. Definim o navă linie ($L$) ca un set de pătrățele umbrite, consecutive pe un rând al foii de matematică. Definim o navă coloană ($C$) ca un set de pătrățele umbrite, consecutive pe o coloană a foii de matematică. Dimensiunea unei nave este egală cu numărul de pătrățele din care este formată. O navă formată dintr-un singur pătrățel nu este nici linie, nici coloană. Navele pot avea diferite dimensiuni. Două nave diferite nu se ating pe laturi sau colțuri, nu se suprapun și nu au pătrățele comune. Pe foaia de matematică sunt pictate doar nave de cele 3 tipuri: navă linie ($L$), navă coloană ($C$) sau navă pătrățel.

Cerință

Cunoscându-se $M$, $N$ și pictura lui Alex, scrieți un program care să determine:

1. Numărul de nave formate doar dintr-un singur pătrățel;
2. Numărul de nave linie și numărul de nave coloană, precum și dimensiunile acestora.

Date de intrare

Fişierul de intrare boats.in conţine pe prima linie un număr natural $P$ reprezentând cerinţa care trebuie să fie rezolvată ($1$ sau $2$). Pe cea de a doua linie fișierul conține două numere întregi, separate printr-un spațiu, reprezentând valorile $M$ și $N$ din enunț. Pe următoarele $M$ linii se află câte N valori egale cu $0$ sau $1$, separate prin câte un spațiu ($0$ - dacă pătrățelul nu face parte dintr-o navă, $1$ - în cazul în care pătrățelul este o parte a unei nave).

Date de ieșire

Dacă cerința este $P = 1$, atunci pe prima linie a fișierului boats.out va fi scris un număr natural reprezentând numărul de nave formate dintr-un singur pătrățel.

Dacă cerința este $P = 2$, aunci în fișierul boats.out vor fi scrise, pe câte o linie, separate prin câte un spațiu, trei valori: caracterul $L$ urmat de numerele $d$ și $c$, în ordine crescătoare după valoarea $d$, unde $d$ - reprezintă lungimea navei (numărul de pătrățele) iar $c$ - numărul de nave linie de lungime $d$. Apoi, pe fiecare dintre liniile următoare vor fi scrise, separate prin câte un spațiu, caracterul $C$ urmat de două numere: $d$ și $c$, în ordine crescătoare după $d$, unde $d$ - reprezintă lungimea navei (numărul de pătrățele) și $c$ - numărul de nave coloană de lungime $d$.

Restricții și precizări

• $2 \leq M, N \leq 1 \ 000$
• Se garantează existența a cel puțin unei nave.
• Pentru rezolvarea corectă a primei cerinţe se va acorda $20\%$ din punctaj, iar pentru rezolvarea corectă a celei de a doua cerințe se va acorda $80\%$ din punctaj.

Exemplul 1

boats.in

1
12 12
0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0

boats.out

1

Explicație

Se rezolvă doar cerința $1$.
Există o singură navă formatată dintr-un singur pătrățel.

$0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1\\ 0 \ 1 \ 1 \ 1 \ 1 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \colorbox{yellow}{\color{black}1} 0 \ 0 \ 0 \ 1\\ 0 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\ 0 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0\\ 0 \ 1 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\$

Exemplul 2

boats.in

2
12 12
0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0

boats.out

L 2 1
L 5 1
L 6 1
C 3 2
C 4 1

Explicație

Se rezolvă doar cerința $2$.
Există $3$ nave linie: o navă linie de lungime $2$, o navă linie de lungime $5$ și o navă linie de lungime $6$.
Există $3$ nave coloană: $2$ nave coloană de lungime $3$, o navă coloană de lungime $4$.

$0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ \color{grey}1\color{white}\\ 0 \colorbox{yellow}{\color{black}1 1 1 1 1} 0 \ 0 \ 0 \ 0 \ 0 \ \color{grey}1\color{white}\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ \color{grey}1\color{white}\\ 0 \ \color{grey}1\color{white} \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\ 0 \ \color{grey}1\color{white} \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\ 0 \ \color{grey}1\color{white} \ 0 \colorbox{yellow}{\color{black}1 1 1 1 1 1} 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ \color{grey}1\color{white} \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ \color{grey}1\color{white} \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ \color{grey}1\color{white} \ 0 \ 0 \ 0 \ 0\\ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ \color{grey}1\color{white} \ 0 \ 0 \ 0 \ 0\\ 0 \colorbox{yellow}{\color{black}1 1} 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0\\$