Blackhawk

Recent, Bob s-a alăturat marinei de război a României, iar acesta a fost încredințat cu sarcina de a pilota un elicopter. În prima lui misiune, el va zbura deasupra unei zone care se află în prezent într-un conflict. Se dă harta topografică a acestui perimetru sub forma unei matrici $N$ x $M$, unde poziția $(i, j)$ în aceasta reprezintă înălțimea în acel punct.
Elicopterul se poate deplasa în nord, sud, est, vest, sus si jos cu o unitate, fiecare mișcare luând timpul de o secundă. Însă acesta nu are voie să iasă din această zonă, fiind extrem de periculos.
După cum știm cu toții, Bob este o persoană foarte precaută. El vrea să afle cât de mult îi ia să ajungă la sol în orice scenariu, în caz de o situație urgentă ( știm că Bob a ajuns la sol dacă altitudinea lui curentă coincide cu cea a poziției pe care se află ).

Cerință

Pentru orice poziție $(i, j)$ unde $1 \leq i \leq N$ și $1 \leq j \leq M$, află timpul minim de a ateriza știind că Bob se află la altitudinea $H$, deasupra tuturor altitudinilor din matrice.$^†$

Date de intrare

Prima linie conține un singur număr $T$ - numărul de teste. Descrierea unui test este următoarea:
Prima linie conține trei numere întregi, $N$, $M$ și $H$. Pe următoarele $N$ linii se află câte $M$ valori, fiecare reprezentând înălțimea în acel punct.

Date de ieșire

Pentru fiecare test afișați răspunsul dorit, după următorul format:
Câte $N$ linii pe care se află câte $M$ valori, fiecare reprezentând timpul minim de aterizare din acel punct.

Restricții și precizări

$\textcolor{red}{Atenție!}$ Din cauza numărului mare de date de intrare, respectiv ieșire, vă recomandăm să adăugați următoarele linii de cod la începutul funcției main().

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

• $1 \leq T \leq 10^6$
• $1 \leq N \leq 10^6 , 1 \leq M \leq 10^6$
• Notăm cu $S$ suma valorilor lui $N×M$ peste toate testele
• $1 \leq S \leq 10^6$
• $1 \leq H \leq 10^7$
• $0 \leq$ numerele din matrice $< H$
• $H$ > valoarea maximă din matrice$^†$

  #	Punctaj	Restricții
  1	14	$S \leq 10^3$
  2	18	$H \leq 10$
  3	20	$N = 1$
  4	48	fără alte restricții

Exemplu

stdin

2
2 2 5
0 1
2 3
5 5 6
2 0 1 2 0 
5 5 1 3 2 
1 0 3 0 0 
4 4 3 5 0 
4 0 3 0 4 

stdout

4 3 
3 2 
2 2 3 4 5 
1 1 2 3 4 
2 2 3 2 3 
2 2 2 1 2 
2 3 3 2 2  

Explicație

În primul test, un exemplu de strategie ar fi următorul:

• decolează la (1, 1), aterizează la (2, 1)
• decolează la (1, 2), aterizează la (2, 2)
• decolează la (2, 1), aterizează la (2, 1)
• decolează la (2, 2), aterizează la (2, 2)