Matrice2

Matrice 2

== 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 ({$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.
 
Aflaţi răspunsul pentru fiecare dintre cele $Q$ întrebări.

h2. Date de intrare

Pe prima linie a fişierului de intrare $matrice.in$ se află $2$ numere întregi $N$ si $Q$ cu semnificaţia din enunţ. Pe următoarele $N$ linii se află câte $N$ numere întregi reprezentând matricea primită de Laura. Fiecare dintre următoarele $Q$ linii conţine câte patru numere întregi $x1 y1 x2 y2$ care descriu câte o întrebare.

Pe prima linie a fişierului de intrare $matrice2.in$ se află $2$ numere întregi $N$ si $Q$ cu semnificaţia din enunţ. Pe următoarele $N$ linii se află câte $N$ numere întregi reprezentând matricea primită de Laura. Fiecare dintre următoarele $Q$ linii conţine câte patru numere întregi {$x{~1~}$} {$y{~1~}$} {$x{~2~}$} {$y{~2~}$} care descriu câte o întrebare.

h2. Date de ieşire

În fişierul de ieşire $matrice.out$ se află răspunsul la cele $Q$ întrebări, câte unul pe linie, în aceeaşi ordine în care au apărut în fişierul de intrare.

În fişierul de ieşire $matrice2.out$ se află răspunsul la cele $Q$ întrebări, câte unul pe linie, în aceeaşi ordine în care au apărut în fişierul de intrare.

* $1 ≤ N ≤ 300$
* $1 ≤ Q ≤ 20.000$

* Elementele matricei sunt numere întregi cuprinse între $1$ şi $1 000 000$.

* Elementele matricei sunt numere întregi cuprinse între $1$ şi $1.000.000$.

* Pentru $15%$ din teste $N ≤ 50$, $Q ≤ 10$ şi valorile matricei sunt cuprinse între $1$ şi $250$.
* Pentru alte $20%$ din teste $N ≤ 100$, $Q ≤ 100$.

* Nu există nicio întrebare pentru care perechea $(x1, y1)$ să coincidă cu perechea $(x2, y2)$.

* Nu există nicio întrebare pentru care perechea ({$x{~1~}$}, {$y{~1~}$}) să coincidă cu perechea ({$x{~2~}$}, {$y{~2~}$}).

h2. Exemplu

3933