== include(page="template/taskheader" task_id="matrice2") ==

Laura a primit de ziua ei o matrice pătratică de dimensiuni $NxN$ de numere întregi. Neştiind ce să facă cu ea, a început să-şi pună diverse întrebări. Fata consideră că un drum de la ({$x{~1~}$}, {$y{~1~}$}) la ({$x{~2~}$}, {$y{~2~}$}) este o secvenţă de celule care începe în celula ({$x{~1~}$}, {$y{~1~}$}), se termină în ({$x{~2~}$}, {$y{~2~}$}) şi oricare două celule consecutive au o latură în comun (deplasarea se poate face spre nord, est, sud, vest). Laura a definit costul unui drum ca fiind valoarea minimă a unei celule de pe acel drum. Apoi ea a început să-şi pună $Q$ întrebări de forma: _Care este costul maxim pe care îl poate avea un drum de la ({$x{~1~}$}, {$y{~1~}$}) la ({$x{~2~}$}, {$y{~2~}$})?_ Întrebările au început să i se pară dificile şi vă cere ajutorul.

Laura a primit de ziua ei o matrice pătratică de dimensiuni $NxN$ de numere întregi. Neştiind ce să facă cu ea, a început să-şi pună diverse întrebări. Fata consideră că un drum de la $(x1, y1)$ la $(x2, y2)$ este o secvenţă de celule care începe în celula ({$x{~1~}$}, {$y{~1~}$}), se termină în ({$x{~2~}$}, {$y{~2~}$}) şi oricare două celule consecutive au o latură în comun (deplasarea se poate face spre nord, est, sud, vest). Laura a definit costul unui drum ca fiind valoarea minimă a unei celule de pe acel drum. Apoi ea a început să-şi pună $Q$ întrebări de forma: _Care este costul maxim pe care îl poate avea un drum de la ({$x{~1~}$}, {$y{~1~}$}) la ({$x{~2~}$}, {$y{~2~}$})?_ Întrebările au început să i se pară dificile şi vă cere ajutorul.

Aflaţi răspunsul pentru fiecare dintre cele $Q$ întrebări.

3933