Fişierul intrare/ieşire:	matrice2.in, matrice2.out	Sursă	ONI 2009, clasele 11-12
Autor	Paul-Dan Baltescu	Adăugată de	Andrei Misarca •Mishu91
Timp execuţie pe test	0.575 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Matrice 2

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₁, y₁) la (x₂, y₂) este o secvenţă de celule care începe în celula (x₁, y₁), se termină în (x₂, y₂) ş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₁, y₁) la (x₂, y₂)? Întrebările au început să i se pară dificile şi vă cere ajutorul.

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

Date de intrare

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₁ y₁ x₂ y₂ care descriu câte o întrebare.

Date de ieşire

Î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.

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 (x₁, y₁) să coincidă cu perechea (x₂, y₂).

Exemplu

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

Cum se trimit solutii?