#include <bit>
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <queue>
#include <array>
#include <cassert>

using namespace std;

[[noreturn]] void usage()
{
    cerr << "Usage: ./generator seed mode n q" << endl;
    exit(1);
}

mt19937 r_dev;
mt19937_64 r_dev64;
// Returns a value in range [0, 1[
double rnd()
{
    return uniform_real_distribution<double>(0, 1)(r_dev);
}
// Returns a value in range [a, b] inclusive
int rnd(int a, int b)
{
    return uniform_int_distribution<int>(a, b)(r_dev);
}
long long rnd64(long long a, long long b)
{
    return uniform_int_distribution<long long>(a, b)(r_dev64);
}
// Returns either 0 or 1
int coin()
{
    return rnd(0, 1);
}
// Shuffles any type with begin and end
template <typename T>
void shuffle(T &arr)
{
    shuffle(arr.begin(), arr.end(), r_dev);
}

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

// corners counterclockwise
const int cx[4] = {1, -1, -1, 1};
const int cy[4] = {1, 1, -1, -1};

struct Query {
    int r1, c1, r2, c2;
};

struct Instance {
    int n, q;
    vector<string> g;
    vector<Query> queries;

    Instance(int _n, int _q) : n(_n), q(_q), g(_n, string(_n, '.')) {}

    bool in_bounds(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }

    void print() {
        cout << n << ' ' << q << '\n';
        for (int i = 0; i < n; ++i) {
            cout << g[i] << '\n';
        }
        for (auto [r1, c1, r2, c2] : queries) {
            cout << r1+1 << " " << c1+1 << " " << r2+1 << " " << c2+1 << '\n';
        }
    }

    void shuffle_queries() {
        shuffle(queries);
        for (auto &query : queries) {
            if (coin()) {
                swap(query.r1, query.r2);
                swap(query.c1, query.c2);
            }
        }
    }

    void gen_random_tree(int target=1e9) {
        vector<vector<bool>> vis(n, vector<bool>(n, 0));

        vector<int> w(n*n);
        iota(w.begin(), w.end(), 0);
        shuffle(w);

        int x0 = rnd(1, n-2);
        int y0 = rnd(1, n-2);
        priority_queue<array<int, 3>> pq;
        pq.push({w[n*x0 + y0], x0, y0});

        int filled = 0;

        while (pq.size() && filled < target) {
            auto [_, x, y] = pq.top();
            pq.pop();
            vis[x][y] = 1;

            int adj = 0;
            int cor = 0;

            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)
                    adj += g[x2][y2] == '#';
            }

            for (int i = 0; i < 4; ++i) {
                int x2 = x + cx[i];
                int y2 = y + cy[i];
                if (0 <= x2 && x2 < n && 0 <= y2 && y2 < n)
                    adj += g[x2][y2] == '#' && g[x][y2] == '.' && g[x2][y] == '.';
            }

            if (adj > 1 || cor > 0) continue;
            g[x][y] = '#';
            filled++;

            for (int i = 0; i < 4; ++i) {
                int x2 = x + dx[i];
                int y2 = y + dy[i];

                if (1 <= x2 && x2 < n-1 && 1 <= y2 && y2 < n-1 && !vis[x2][y2])
                    pq.push({w[n*x2 + y2], x2, y2});
            }
        }
    }

    void monotonic_path(int x1, int y1, int x2, int y2) {
        g[x1][y1] = '#';
        if (x1 == x2 && y1 == y2) return;
        int sx = abs(x1 - x2);
        int sy = abs(y1 - y2);
        bernoulli_distribution d(double(sx) / (sy + sx));
        if (d(r_dev)) {
            if (x2 > x1) monotonic_path(x1+1, y1, x2, y2);
            else monotonic_path(x1-1, y1, x2, y2);
        } else {
            if (y2 > y1) monotonic_path(x1, y1+1, x2, y2);
            else monotonic_path(x1, y1-1, x2, y2);
        }
    }

    void flood_fill() {
        vector<vector<bool>> vis(n, vector<bool>(n, 0));
        vector<pair<int, int>> queue;
        vis[0][0] = 1;
        queue.emplace_back(0, 0);
        for (int qi = 0; qi < (int)queue.size(); ++qi) {
            auto [x, y] = queue[qi];
            for (int i = 0; i < 4; ++i) {
                int tx = x + dx[i], ty = y + dy[i];
                if (in_bounds(tx, ty) && g[tx][ty] == '.' && !vis[tx][ty]) {
                    vis[tx][ty] = 1;
                    queue.emplace_back(tx, ty);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                g[i][j] = vis[i][j] ? '.' : '#';
            }
        }
    }

    void gen_convex() {
        int a = rnd(1, n-2);
        int b = rnd(1, n-2);
        int c = rnd(1, n-2);
        int d = rnd(1, n-2);
        monotonic_path(1, a, b, n-2);
        monotonic_path(b, n-2, n-2, c);
        monotonic_path(n-2, c, d, 1);
        monotonic_path(d, 1, 1, a);
        flood_fill();
    }

    // ensure land touches edges (?), then invert all interior cells
    void invert() {
        int x0 = -1, y0 = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == '#') {
                    x0 = i;
                    y0 = j;
                    break;
                }
            }
            if (x0 != -1) break;
        }
        assert(x0 != -1);
        for (int i = 1; i < x0; ++i) g[i][y0] = '#';
        for (int i = 1; i < n-1; ++i) {
            for (int j = 1; j < n-1; ++j) {
                if (g[i][j] == '#') g[i][j] = '.';
                else g[i][j] = '#';
            }
        }
    }

    void pad(int h) {
        assert(!queries.size());
        int nn = n + 2*h;
        for (int i = 0; i < n; ++i) {
            g[i].resize(nn, '.');
            rotate(g[i].begin(), g[i].begin() + n + h, g[i].end());
        }
        g.resize(nn, string(nn, '.'));
        rotate(g.begin(), g.begin() + n + h, g.end());
        n = nn;
    }

    void random_queries() {
        vector<pair<int, int>> land;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == '#') land.push_back({i, j});
            }
        }
        assert(land.size());
        while ((int)queries.size() < q) {
            int a = rnd(0, land.size()-1);
            int b = rnd(0, land.size()-1);
            queries.push_back({land[a].first, land[a].second, land[b].first, land[b].second});
        }
    }

    void random_rows() {
        int la = 1, lb = n-2;
        for (int i = 1; i < n-1; ++i) {
            int a, b;
            do {
                a = rnd(1, lb);
                b = rnd(la, n-2);
            } while (a > b);
            for (int j = a; j <= b; ++j) g[i][j] = '#';
            la = a; lb = b;
        }
    }

    void random_grow(int max_deg) {
        vector<vector<bool>> vis(n, vector<bool>(n, 0));

        vector<int> w(n*n);
        iota(w.begin(), w.end(), 0);
        shuffle(w);

        int x0 = rnd(1, n-2);
        int y0 = rnd(1, n-2);
        priority_queue<array<int, 3>> pq;
        pq.push({w[n*x0 + y0], x0, y0});

        auto deg = [&](int x, int y) {
            int d = 0;
            for (int i = 0; i < 4; ++i) {
                int tx = x + dx[i], ty = y + dy[i];
                if (in_bounds(tx, ty) && g[tx][ty] == '#') d++;
            }
            return d;
        };

        auto allowed = [&](int x, int y) {
            if (g[x][y] == '#') return false;
            int n_max_deg = 0;
            for (int i = 0; i < 4; ++i) {
                int tx = x + dx[i], ty = y + dy[i];
                n_max_deg = max(n_max_deg, deg(tx, ty));
            }
            if (n_max_deg >= max_deg) return false;
            int z[8];
            for (int i = 0; i < 4; ++i) {
                z[2*i] = g[x + dx[i]][y + dy[i]] == '#';
                z[2*i+1] = g[x + cx[i]][y + cy[i]] == '#';
            }
            int changes = 0;
            for (int i = 0; i < 8; ++i) {
                changes += z[i] != z[(i+1)%8];
            }
            if (changes > 2) return false;
            return true;
        };

        while (pq.size()) {
            auto [_, x, y] = pq.top();
            pq.pop();
            vis[x][y] = 1;
            if (!allowed(x, y)) continue;
            g[x][y] = '#';
            for (int i = 0; i < 4; ++i) {
                int x2 = x + dx[i];
                int y2 = y + dy[i];

                if (1 <= x2 && x2 < n-1 && 1 <= y2 && y2 < n-1 && !vis[x2][y2])
                    pq.push({w[n*x2 + y2], x2, y2});
            }
        }
    }

    void snake_grow(int corridor_width) {
        int pat_w = 2 * corridor_width + 2;
        int pat_half = corridor_width + 1;

        vector<vector<bool>> vis(n, vector<bool>(n, 0));

        vector<int> w(n*n);
        iota(w.begin(), w.end(), 0);
        shuffle(w);

        auto allowed = [&](int x, int y) {
            if (g[x][y] == '#') return false;
            // Block certain areas to make snake-ish shape
            if (y % pat_w == pat_half && x <= 9*n/10) return false;
            if (y % pat_w == 0 && x > n/10) return false;
            int z[8];
            for (int i = 0; i < 4; ++i) {
                z[2*i] = g[x + dx[i]][y + dy[i]] == '#';
                z[2*i+1] = g[x + cx[i]][y + cy[i]] == '#';
            }
            int changes = 0;
            for (int i = 0; i < 8; ++i) {
                changes += z[i] != z[(i+1)%8];
            }
            if (changes > 2) return false;
            return true;
        };

        int x0, y0;
        do {
            x0 = rnd(1, n-2);
            y0 = rnd(1, n-2);
        } while (!allowed(x0, y0));
        priority_queue<array<int, 3>> pq;
        pq.push({w[n*x0 + y0], x0, y0});

        while (pq.size()) {
            auto [_, x, y] = pq.top();
            pq.pop();
            vis[x][y] = 1;
            if (!allowed(x, y)) continue;
            g[x][y] = '#';
            for (int i = 0; i < 4; ++i) {
                int x2 = x + dx[i];
                int y2 = y + dy[i];

                if (1 <= x2 && x2 < n-1 && 1 <= y2 && y2 < n-1 && !vis[x2][y2])
                    pq.push({w[n*x2 + y2], x2, y2});
            }
        }
    }

    void snake(bool shortcuts=false) {
        int side = 1;
        for (int x = 1; x < n-1; x += 2) {
            for (int y = 1; y < n-1; ++y) g[x][y] = '#';
            if (x > 2) {
                int fillcount = shortcuts ? rnd(1, n/10) : 1;
                for (int y = 0; y < fillcount; ++y) {
                    g[x-1][side ? n-2-y : 1+y] = '#';
                }
                side = !side;
            }
        }
        if (n%2 == 0) {
            g[n-2][n-2] = '#';
        }
    }

    // Returns innermost point
    pair<int, int> spiral(int sx, int sy, int w) {
        if (w == 1) {
            g[sx][sy] = '#';
            return {sx, sy};
        } else if (w == 2) {
            g[sx][sy] = g[sx][sy+1] = g[sx+1][sy+1] = '#';
            return {sx+1, sy+1};
        }
        for (int i = 0; i < w-1; ++i) g[sx][sy + i] = '#';
        for (int i = 0; i < w-1; ++i) g[sx + i][sy + w-1] = '#';
        for (int i = 1; i < w; ++i) g[sx + w-1][sy + i] = '#';
        for (int i = 2; i < w; ++i) g[sx + i][sy] = '#';
        if (w >= 5) {
            g[sx+2][sy+1] = '#';
            return spiral(sx+2, sy+2, w-4);
        } else return {sx+2, sy};
    }

    void comb(int y0, int y1) {
        int layers = bit_width((unsigned)n);
        int step = abs(y1-y0) / layers;
        int dir = y0 < y1 ? 1 : -1;
        int stepc = 0;
        for (int y = y0; ; y += dir) {
            int on = coin();
            for (int x = 1; x < n-1; ++x) {
                if (g[x][y-dir] == '#' || y == y1) g[x][y] = '#';
                else if (stepc == 0) {
                    if (on) g[x][y] = '#';
                    on = !on;
                }
            }
            stepc = (stepc + 1) % step;
            if (y == y1) break;
        }
    }

    int hammer(int head_width) {
        for (int x = 1; x < n-1; ++x) {
            for (int y = 1; y <= head_width; ++y) {
                g[x][y] = '#';
            }
        }
        int hx = rnd(1, n-2);
        for (int y = 1; y < n-1; ++y) g[hx][y] = '#';
        return hx;
    }
};

int main(int argc, char **argv)
{
    // Check argument count
    if (argc < 5)
        usage();

    // Parse arguments into numbers
    unsigned long long seed = stoull(argv[1]);
    r_dev.seed(seed);
    r_dev64.seed(seed);
    string mode = argv[2];
    int n = atoi(argv[3]);
    int q = atoi(argv[4]);

    if (mode == "random-tree") {
        Instance inst(n, q);
        inst.gen_random_tree();
        inst.random_queries();
        inst.print();
    } else if (mode == "convex") {
        Instance inst(n, q);
        inst.gen_convex();
        inst.random_queries();
        inst.print();
    } else if (mode == "hammer") {
        Instance inst(n, q);
        int hx = inst.hammer(n-20);
        inst.random_queries();
        inst.print();
    } else if (mode == "random-inv") {
        Instance inst(n-2, q);
        inst.gen_random_tree((n-2) * (n-2) * 0.45);
        inst.pad(1);
        inst.invert();
        inst.random_queries();
        inst.print();
    } else if (mode == "random-rows") {
        Instance inst(n, q);
        inst.random_rows();
        inst.random_queries();
        inst.print();
    } else if (mode == "grow-deg3") {
        Instance inst(n, q);
        inst.random_grow(3);
        inst.random_queries();
        inst.print();
    } else if (mode == "grow-deg4") {
        Instance inst(n, q);
        inst.random_grow(4);
        inst.random_queries();
        inst.print();
    } else if (mode == "snake-grow") {
        int corridor_width = atoi(argv[5]);
        Instance inst(n, q);
        inst.snake_grow(corridor_width);
        inst.random_queries();
        inst.print();
    } else if (mode == "snake") {
        Instance inst(n, q);
        inst.snake();
        inst.queries.push_back({1, 1, n-2, n-2});
        inst.random_queries();
        inst.shuffle_queries();
        inst.print();
    } else if (mode == "snake-highans") {
        Instance inst(n, q);
        inst.snake();
        while ((int)inst.queries.size() < int(0.95 * q)) {
            inst.queries.push_back({1, rnd(1, n-2), n-3+n%2, rnd(1, n-2)});
        }
        inst.random_queries();
        inst.shuffle_queries();
        inst.print();
    } else if (mode == "snake-highans-nontree") {
        Instance inst(n, q);
        inst.snake(true);
        while ((int)inst.queries.size() < int(0.9 * q)) {
            inst.queries.push_back({1, rnd(1, n-2), n-3+n%2, rnd(1, n-2)});
        }
        inst.random_queries();
        inst.shuffle_queries();
        inst.print();
    } else if (mode == "comb-left") {
        Instance inst(n, q);
        inst.comb(1, n-2);
        inst.random_queries();
        inst.print();
    } else if (mode == "comb-right") {
        Instance inst(n, q);
        inst.comb(n-2, 1);
        inst.random_queries();
        inst.print();
    } else if (mode == "comb-both") {
        Instance inst(n, q);
        inst.comb(1, n/2);
        inst.comb(n/2+1, n-2);
        inst.random_queries();
        inst.print();
    } else if (mode == "spiral") {
        Instance inst(n, q);
        auto [r2, c2] = inst.spiral(1, 1, n-2);
        inst.queries.push_back({1, 1, r2, c2});
        inst.random_queries();
        inst.shuffle_queries();
        inst.print();
    } else usage();

    return 0;
}
