matrice

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.

Cerinţă

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

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.

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.

Restricţii şi precizări

• 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).

Exemplu

matrice.in

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	

matrice.out

5
6
1

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