Cerința

Se consideră o clădire de formă dreptunghiulară, împărțită în n*m camere, dispuse sub forma unei matrice cu n linii și m coloane. Dintr-o cameră se poate trece în oricare dintre cele 4 camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.

În anumite camere se află echipe de pompieri. Pentru o intervenție cât mai rapidă în cazul unui eventual incendiu apărut în una dintre camerele clădirii, este necesar să se știe, pentru fiecare cameră care este timpul minim în care o echipă de pompieri ajunge în acea cameră.

Date de intrare

Fișierul de intrare acces1.in conține pe prima linie numerele n m; următoarele n linii conțin câte m caractere, care pot fi:

• - – reprezintă o cameră liberă
• # – reprezintă o cameră închisă
• P – reprezintă o cameră în care se găsește o echipă de pompieri

Date de ieșire

Fișierul de ieșire acces1.out va conține o matrice cu n linii și m coloane, fiecare element al matricei reprezentând timpul minim necesar ca o echipă de pompieri să ajungă în camera corespunzătoare. Pentru camerele ocupate se va fișa simbolul #, iar pentru cele libere în care nu va ajunge nici o echipă se va afișa -.
Matricea va fi afișată linie cu linie, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n,m ≤ 1000

Exemplu:

acces1.in

4 6
P-#-#P
--##--
--P---
-----#

acces1.out

0 1 # - # 0 
1 2 # # 2 1 
2 1 0 1 2 2 
3 2 1 2 3 #