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ă doua 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
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).