== 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 $(x1, y1)$ la $(x2, y2)$ este o secvenţă de celule care începe în celula $(x1, y1)$, se termină în $(x2, y2)$ ş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 $(x1, y1)$ la $(x2, y2)$?_ Întrebările au început să i se pară dificile şi vă cere ajutorul. Aflaţi răspunsul pentru fiecare dintre cele $Q$ întrebări.

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 $(x1, y1)$, se termină în $(x2, y2)$ ş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 $(x1, y1)$ la $(x2, y2)$?_ Întrebările au început să i se pară dificile şi vă cere ajutorul.
 
Aflaţi răspunsul pentru fiecare dintre cele $Q$ întrebări.

h2. Date de intrare