#include "cseslib.hpp"
#include <iostream>
#include <vector>

void failmsg(string msg="") {
    if (msg != "") cerr << msg << endl;
    fail();
}

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    auto nq = read_ints(2, 1, 1e5);
    auto n = nq[0];
    auto q = nq[1];

    if (n < 3 || n > 1000) failmsg("n out of bounds");

    vector<string> g(n);

    for (int i = 0; i < n; ++i) {
        g[i] = read_str(n, n, ".#");
    }

    for (int i = 0; i < n; ++i) {
        if (g[0][i] != '.' || g[n-1][i] != '.' ||
            g[i][0] != '.' || g[i][n-1] != '.') failmsg("edges not water");
    }

    bool is_tree = true;
    for (int i = 1; i < n-1; ++i) {
        for (int j = 1; j < n-1; ++j) {
            if (g[i][j] == '#' && g[i+1][j] == '#' &&
                g[i][j+1] == '#' && g[i+1][j+1] == '#') is_tree = false;
        }
    }

    bool contiguous_rows = true;
    for (int i = 0; i < n; ++i) {
        int state = 0;
        for (int j = 0; j < n; ++j) {
            if (state % 2 != (g[i][j] == '#')) state++;
        }
        if (state >= 3) contiguous_rows = false;
    }
    bool contiguous_columns = true;
    for (int j = 0; j < n; ++j) {
        int state = 0;
        for (int i = 0; i < n; ++i) {
            if (state % 2 != (g[i][j] == '#')) state++;
        }
        if (state >= 3) contiguous_columns = false;
    }

    int max_deg = 0;
    for (int i = 1; i < n-1; ++i) {
        for (int j = 1; j < n-1; ++j) {
            int deg = 0;
            for (int d = 0; d < 4; ++d) {
                int x = i+dx[d], y = j+dy[d];
                if (g[x][y] == '#') deg++;
            }
            max_deg = max(max_deg, deg);
        }
    }

    for (int i = 0; i < q; ++i) {
        auto l = read_ints(4, 1, n);
        auto r1 = l[0];
        auto c1 = l[1];
        auto r2 = l[2];
        auto c2 = l[3];

        if (g[r1-1][c1-1] == '.' || g[r2-1][c2-1] == '.')
            failmsg("query point in water");
    }

    vector<vector<bool>> vis(n, vector<bool>(n, 0));
    int visc = 0;

    for (char t : string(".#")) {
        int x0 = 0, y0 = 0;
        while (x0 < n && g[x0][y0] != t) {
            if (++y0 == n) {
                y0 = 0;
                ++x0;
            }
        }

        if (x0 == n) fail();

        vector<pair<int, int>> st;
        st.push_back({x0, y0});
        vis[x0][y0] = 1;
        ++visc;

        while (st.size()) {
            auto [x, y] = st.back();
            st.pop_back();

            for (int i = 0; i < 4; ++i) {
                int x2 = x + dx[i];
                int y2 = y + dy[i];
                if (0 <= x2 && x2 < n && 0 <= y2 && y2 < n && g[x2][y2] == t && !vis[x2][y2]) {
                    st.push_back({x2, y2});
                    vis[x2][y2] = 1;
                    ++visc;
                }
            }
        }
    }

    if (visc != n * n)
        failmsg("non-contiguous");

    vector<int> groups;
    if (n <= 200 && q <= 200) groups.push_back(1);
    if (contiguous_rows && contiguous_columns) groups.push_back(2);
    if (is_tree) groups.push_back(3);
    if (contiguous_rows) groups.push_back(4);
    // if (max_deg <= 3) groups.push_back(5);
    groups.push_back(5);

    end_groups(groups);
}
