#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("matrice2.in");
ofstream g("matrice2.out");
#define nmax (302*302)
#define ll long long
#define Ceva 17
#define inf (1<<29)
const int dx[] = {0, -1, 0, 1};
const int dy[] = {-1, 0, 1, 0};
int n, m, P[nmax], U[nmax], viz[nmax], t[nmax], secv[nmax*2], nivel[nmax], Min[Ceva][nmax*2], Nod[Ceva][nmax*2];
int rezMin[Ceva][nmax], cine[Ceva][nmax];
vector< pair<int,int> > gf[nmax];
int cnt;
pair< pair<int,int>, int> v[nmax*4];
int a[303][303];
void citeste(){
f >> n >> m;
int k = 0;
for(int i=1; i<=n; ++i){
int linie = 0;
if (i & 1) linie = 1;
for(int j=1; j<=n; ++j){
++k;
//f >> a[linie][j];
f >> a[i][j];
//fac muchiile
//if (k - n > 0) v[++cnt] = make_pair( make_pair(k, k-n), min(a[linie][j], a[1-linie][j]) );
//if (j - 1 > 0) v[++cnt] = make_pair( make_pair(k, k-1), min(a[linie][j], a[linie][j-1]) );
}
}
}
void transforma(int x1, int y1, int x2, int y2, int &i, int &j){
i = (n * x1) - (n - y1);
j = (n * x2) - (n - y2);
}
inline bool check(int x, int y){
if (x > 0 && y > 0 && x <= n && y <= n) return 1;
return 0;
}
void fa_graf(){
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
for(int k=0; k<4; ++k){
int new_i = i + dx[k];
int new_j = j + dy[k];
if (check(new_i, new_j) ){
int x = 0; int y = 0;
transforma( i, j, new_i, new_j, x, y );
v[++cnt] = make_pair( make_pair(x, y), min(a[i][j], a[new_i][new_j]) );
}
}
}
}
}
bool cmp( pair< pair<int,int>, int> a, pair< pair<int,int>, int > b){
return (a.second > b.second);
}
int afla(int x){
int cpy = x;
for(; t[x] != 0; x=t[x]);
while(cpy != x){
int unde = t[cpy];
t[cpy] = x;
cpy = unde;
}
return x;
}
void uneste(int x, int y){
t[x] = y;
}
void fa_apm(){
//fac apm de cost maxim
sort(v+1, v+cnt+1, cmp);
for(int i=1; i<=cnt; ++i){
int x = v[i].first.first;
int y = v[i].first.second;
int c = v[i].second;
int radx = afla(x); int rady = afla(y);
if (radx == rady) continue;// sunt in aceeasi componenta
uneste(radx, rady);
//cout << x << " " << y << " " << c << "\n";
gf[x].push_back( make_pair(y, c) );
gf[y].push_back( make_pair(x, c) );
}
}
void init(int tata, int nod, int cost){
rezMin[0][nod] = cost;
cine[0][nod] = tata;// cien ii al 2 ^ 0 tata pt nod
}
void dfs(int nod, int niv){
viz[nod] = 1;
secv[++secv[0]] = nod;
P[nod] = secv[0];
nivel[nod] = niv;
for(int i=0; i<gf[nod].size(); ++i){
int vc = gf[nod][i].first;
if (viz[vc] == 0){
init(nod, vc, gf[nod][i].second);//initializez rmq-ul pt muchia minima
dfs(vc, niv+1);
secv[ ++secv[0] ] = nod;
//U[nod] = secv[0];
}
}
//U[nod] = secv[0];
}
void fa_lca(){
//elementul cu nivelul minim din intervalul P[x], U[x]
for(int i=1; i<=secv[0]; ++i){
Min[0][i] = nivel[ secv[i] ];//nivelul pe care se afla
Nod[0][i] = secv[i];// nodul care se afla
}
for(int i=1; i<17; ++i){
int put = (1<<i);
for(int j=1; j<=secv[0]; ++j){
int Y = j + put - 1;// el tine pe intervalul [j, Y];
int X = Y - ( 1<<(i-1) ) + 1;
Min[i][j] = Min[i-1][j];
Nod[i][j] = Nod[i-1][j];
if (Min[i][j] > Min[i-1][X]){
Min[i][j] = Min[i-1][X];
Nod[i][j] = Nod[i-1][X];
}
}
}
//cam atat
}
void fa_muchie(){
//acum aflu muchia minima
for(int i=1; i<17; ++i){
int put = (1<<i);
for(int j=1; j<=n*n; ++j){
int new_x = cine[i-1][j];
cine[i][j] = cine[i-1][new_x];
rezMin[i][j] = min(rezMin[i-1][j], rezMin[i-1][new_x]);
}
}
}
void afla_lca(int &Lca, int x, int y){
int p1 = P[x];
int p2 = P[y];
if (p1 > p2) swap(p1, p2);//daca apara dupa p2
//acum trebuie sa aflu minimul de pe intervalul p1, p2;
int lung = p2 - p1 + 1;
int rez = inf;
for(int i=17; i>=0; --i){
if ( (lung & (1<<i) ) != 0 ){
if (rez > Min[i][p1]){
rez = Min[i][p1];
Lca = Nod[i][p1];
}
p1 = p1 + (1<<i) -1;
}
}
}
void afla_cost(int nod, int lca, int &cost){
int k = nivel[nod] - nivel[lca];// al cate-lea tata e lca
//cout << " K: " << k << " " << nod << " " << lca << "\n";
for(int i=17; i>=0; --i){
if ( ( k & (1<<i) ) != 0 ){
cost = min(cost, rezMin[i][nod]);
nod = cine[i][nod];
}
}
}
void rezolva(){
fa_graf();
fa_apm();
for(int i=0; i<nmax; ++i) t[i] = 0;//numai am nevoie de ei; o sa am nevoie la muchia minima
//initializez pt muchia minima
for(int i=0; i<17; ++i){
for(int j=0; j<nmax; ++j) rezMin[i][j] = inf, Min[i][j] = inf;
}
dfs(1,1);
/*
for(int i=1; i<=n*n; ++i){
cout << nivel[i] << " ";
}
cout << "\n";
*/
fa_lca();
//acum stiu lca;
//acum aflu muchia minima de pe drumul x-lca, y-lca
fa_muchie();
//acum raspund la query-uri
for(int i=1; i<=m; ++i){
int x1, y1, x2, y2;
f >> x1 >> y1 >> x2 >> y2;
int X = 0; int Y = 0;
transforma(x1, y1, x2, y2, X, Y);
//aflu lca-ul dintre X si Y;
int Lca = 0;
afla_lca(Lca, X, Y);
int cost_min = inf;
afla_cost(X, Lca, cost_min);
afla_cost(Y, Lca, cost_min);
//cout << X << " " << Y << " " << Lca << " " << nivel[X] << " " << nivel[Lca] << " " << nivel[Y]<< "\n";
cout << cost_min << "\n";
g << cost_min << "\n";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}
Salajan Razvan vendetta