== 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.
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
Fişierul de intrare $matrice2.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $matrice2.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 300$
* $1 ≤ Q ≤ 20.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)$.
h2. Exemplu
table(example). |_. matrice2.in |_. matrice2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 3
9 5 9 8 7
2 1 1 3 8
1 3 9 4 6
4 1 8 6 7
2 4 5 5 6
1 1 3 3
5 5 1 5
2 2 4 3
|5
6
1
|
h3. Explicaţie
...
Pentru prima întrebare răspunsul este dat de următorul drum:
$**9 5 9 8 7**$
$2 1 1 3 8$
$1 3 9 4 6$
$4 1 8 6 7$
$2 4 5 5 6$
== include(page="template/taskfooter" task_id="matrice2") ==
