#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;
	vector<vector<int>> copii;
	int rad = 0;
	void dfs(const int cur){
		for(const auto next : copii[cur]){
			adanc[next] = adanc[cur] + 1;
			dfs(next); } }
public:
	merge_find(const int N): n(N), tata(n), adanc(n, 1), cst(n), copii(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; }

	void redo(){
		adanc[0] = 0;
		for(int i = 0; i < n; ++i){
			if(tata[i] == i){
				rad = i; }
			else{
				copii[tata[i]].push_back(i); } }
		dfs(rad); }

	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, v[x]); } } } }

	mf.redo();

	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; }