#include <fstream>
#include <iostream>
#include <array>
#include <tuple>
#include <numeric>
#include <vector>
using namespace std;

class merge_find{
	int n;
	vector<int> tata, adanc, cst;
public:
	merge_find(const int N): n(N), tata(n), adanc(n, 1), cst(n){
		iota(begin(tata), end(tata), 0); }
	int find(int x){
		while(x != tata[x]){
			x = tata[x]; }
		return x; }
	void merge(int a, int b, const int c){
		a = find(a), b = find(b);
		if(a == b){
			return; }
		if(adanc[a] < adanc[b]){
			swap(a, b); }
		if(adanc[a] == adanc[b]){
			++adanc[a]; }
		tata[b] = a;
		cst[b] = c; }

	int query(int a, int b){
		int rez = 1000000;
		while(adanc[a] < adanc[b]){
			rez = min(rez, cst[a]);
			a = tata[a]; }
		while(adanc[a] > adanc[b]){
			rez = min(rez, cst[b]);
			b = tata[b]; }
		while(a != b){
			rez = min(rez, cst[a]);
			a = tata[a];
			rez = min(rez, cst[b]);
			b = tata[b]; }
		return rez; } };


constexpr int maxv = 1000010;

int main(){
	ifstream f("matrice2.in");
	ofstream g("matrice2.out");

	int n, q;
	f >> n >> q;

	auto code = [n](const int a, const int b){
		return n*(a-1) + b - 1; };
	auto vecin = [n](const int a, const int d){
		if(d == 0){
			if(a-n < 0){
				return -1; }
			return a-n; }
		if(d == 1){
			if(a+n >= n*n){
				return -1; }
			return a+n; }
		if(d == 2){
			if((a-1)/n != a/n){
				return -1; }
			return a-1; }
		if(d == 3){
			if((a+1)/n != a/n){
				return -1; }
			return a+1; } };

	vector<int> v(n*n);

	static array<vector<int>, maxv> ord;

	for(int i = 0; i < n*n; ++i){
		f >> v[i];
		ord[v[i]].push_back(i); }

	merge_find mf(n*n);

	for(int i = maxv-1; i > 0; --i){
		for(const auto x : ord[i]){
			for(int d = 0, tmp; d < 4; ++d){
				if((tmp = vecin(x, d)) != -1 && v[tmp] >= v[x]){
					mf.merge(x, tmp, i); } } } }

	for(int i = 0, x1, y1, x2, y2; i < q; ++i){
		f >> x1 >> y1 >> x2 >> y2;
		g << mf.query(code(x1, y1), code(x2, y2)) << endl; }


	return 0; }