miex

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

int aib2d[501][501], n, m;

int lsb(int x)
{
    return x & -x;
}

void update(int x, int y, int val)
{
    for(; x <= n; x += lsb(x))
        for(int y1 = y; y1 <= m; y1 += lsb(y1))
            aib2d[x][y1] ^= val;
}

int query(int x, int y)
{
    int s = 0;
    for(; x > 0; x -= lsb(x))
        for(int y1 = y; y1 > 0; y1 -= lsb(y1))
            s ^= aib2d[x][y1];
    return s;
}

vector <int> interes[250001];
vector <pair <int, int>> poz[250001];
int cod[250001];
int check[250001];

struct querr{
    int x1, y1, x2, y2;
    int ind, rasp;
}que[20001];

int main()
{
#ifdef HOME
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // HOME
#ifndef HOME
    freopen("miex.in", "r", stdin);
    freopen("miex.out", "w", stdout);
#endif // HOME
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //srand(time(NULL));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int x;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin >> x;
            poz[x].push_back({i, j});
        }
    for(int i = 1; i <= n * m; i++)
    {
        cod[i] = rng();
        check[i] = check[i - 1] ^ cod[i];
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> que[i].x1 >> que[i].y1 >> que[i].x2 >> que[i].y2;
        que[i].ind = i;
        que[i].rasp = 0;
    }
    for(int pas = 1 << 19; pas > 0; pas /= 2)
    {
        for(int i = 1; i <= q; i++)
            if(que[i].rasp + pas <= n * m)
                interes[que[i].rasp + pas].push_back(i);
        for(int i = 1; i <= n * m; i++)
        {
            for(auto it:poz[i])
                update(it.first, it.second, cod[i]);
            for(auto it:interes[i])
                if((query(que[it].x2, que[it].y2) ^ query(que[it].x1 - 1, que[it].y2) ^ query(que[it].x2, que[it].y1 - 1) ^ query(que[it].x1 - 1, que[it].y1 - 1)) == check[i])
                    que[it].rasp += pas;
            interes[i].clear();
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                aib2d[i][j] = 0;
    }
    for(int i = 1; i <= q; i++)
        cout << que[i].rasp + 1<< '\n';
    return 0;
}