#include <bits/stdc++.h>
using namespace std;

//const int N = 305;
//const int M = 90005;
//int v[N][N], n, q, t[M];
//bool p[N][N];
vector<vector<pair<int, int>>> poz(1000005);
//void Union(int x, int y)
//{
//    t[y] = x;
//}
//int Find(int x)
//{
//    int rad, y;
//    while (t[rad] != 0)
//        rad = t[rad];
//    while (x != rad)
//    {
//        y = t[x];
//        t[x] = rad;
//        x = y;
//    }
//    return rad;
//}
//
//struct arbore
//{
//    int x1, y1, x2, y2, st, dr, p;
//} f[20005];
//unordered_multimap<int, int> m;
//
//int di[] = {-1, 0, 0, 1};
//int dj[] = {0, -1, 1, 0};
//
//void adaugare(int i, int j)
//{
//    int a, b;
//    a = (i - 1) * n + j;
//    cout << i << ' ' << j << endl;
//    for (int k = 0; k < 4; k++)
//    {
//        int ii, jj;
//        ii = i + di[k];
//        jj = j + dj[k];
//            cout << i << ' ' << j << ' ' << ii << ' ' << jj << endl;
//        if (ii >= 1 && jj >= 1 && p[ii][jj])
//        {
//            b = Find((ii - 1) * n + jj);
//            Union(a, b);
//        }
//    }
//    p[i][j] = 1;
//}

int main()
{
//    cin >> n >> q;
//    int nrq = q;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= n; j++)
//        {
//            cin >> v[i][j];
//            poz[v[i][j]].push_back({i, j});
//        }
//    for (int i = 1; i <= q; i++)
//    {
//        cin >> f[i].x1 >> f[i].y1 >> f[i].x2 >> f[i].y2;
//        f[i].st = 1;
//        m.insert({(1 + 1e6) / 2, i});
//        f[i].dr = 1e6;
//    }
//    while (nrq)
//    {
//        for (int i = 1; i < M; i++)
//            t[i] = 0;
//        for (int i = 1; i <= n; i++)
//            for (int j = 1; j <= n; j++)
//                p[i][j] = 0;
//        for (int val = 1; val <= 1000000; val++)
//        {
//            cout << val << endl;
//            for (pair<int, int> aux : poz[val])
//                adaugare(aux.first, aux.second);
//            auto it = m.find(val);
//            while (it != m.end())
//            {
//                int ind = it->second;
//                int a, b;
//                a = (f[ind].x1 - 1) * n + f[ind].y1;
//                b = (f[ind].x2 - 1) * n + f[ind].y2;
//                int mid = (f[ind].st + f[ind].dr) / 2;
//                if (Find(a) == Find(b))
//                {
//                    f[ind].p = mid;
//                    f[ind].dr = mid - 1;
//                }
//                else
//                    f[ind].st = mid + 1;
//                m.erase(it);
//                it = m.find(val);
//                if (f[ind].st > f[ind].dr)
//                {
//                    nrq--;
//                    break;
//                }
//                mid = (f[ind].st + f[ind].dr) / 2;
//                m.insert({mid, ind});
//            }
//        }
//    }
//    for (int i = 1; i <= q; i++)
//        cout << f[i].p << ' ';
    return 0;
}