Mitruţ s-a apucat de curând de pictat matrici. Fiindcă vrea să vadă cât de pricepuţi sunteţi voi la pictură, el vă pune la dispoziţie o matrice cu $N*M$ căsuţe pictate de el. Fiecare căsuţă are o culoare între $0$ şi $K$. Dacă o căsuţă are culoarea $0$, înseamnă că încă nu a fost pictată. Numim o ‘zonă’ de culoare $x$, o submulţime maximală de căsuţe din matrice cu proprietatea că toate au culoarea $x$ şi există drum între oricare două(trecând prin căsuţe adiacente de acceaşi culoare). Se ştie că toate zonele urmează o linie(de grosime $1$) care poate să-şi schimbe direcţia şi să se auto-intersecteze, dar nu se poate dubla(grosimea este $1$ peste tot). Pentru mai multă claritate urmăriţi explicaţiile de mai jos.
Zonă validă de culoare $x$

($2$ auto-intersecţtii, $9$ schimbări de direcţie)

( $2$ auto-intersecţtii, $9$ schimbări de direcţie)

0 0 0 0 x x x x 0
0 0 x 0 x 0 0 x x

h2. Restricţii

•	$1$ ≤ $N$,$M$ ≤ $1000$

•	$1$ ≤ $N$, $M$ ≤ $1000$

h2. Exemplu