1. Abridged Problem Statement
Given an h×w grid of lowercase letters (1≤h,w≤700), find the largest square submatrix such that every row and every column of that square is a palindrome. Output the 1-based coordinates (r1, c1, r2, c2) of any maximum-size solution.

2. Detailed Editorial

Problem restatement
We must pick a k×k square in an h×w letter grid so that for each of its k rows the substring is a palindrome, and for each of its k columns the substring is a palindrome. We want the maximum k, and to report the coordinates of one such square.

Challenges
A brute-force scan for all possible top-left corners and all k (up to 700) is O(h·w·k), up to 700³≈343 million checks—too big under 0.25 s. We need an O((h·w)·log n) or O(h·w) solution.

Key ideas
1. Rolling hashes allow O(1) palindrome tests on any substring. We build forward and reverse hash arrays for each row and each column.
2. For a fixed k, we can mark at each cell (i,j):
   - rowPal[i][j]=1 if row i substring [j…j+k−1] is palindrome
   - colPal[i][j]=1 if column j substring [i…i+k−1] is palindrome
3. We want a k×k square at (i,j) if in that block all k rows are palindrome at column j, and all k columns are palindrome at row i. We can precompute two helper arrays:
   - cntDown[i][j]: how many consecutive rows from i downward have rowPal=1 at (row, j)
   - cntRight[i][j]: how many consecutive columns from j rightward have colPal=1 at (i, col)
   Then square exists when cntDown[i][j]≥k and cntRight[i][j]≥k.
4. We binary-search the half-size, probing both parities (even/odd k) until one is determined. Each check costs O(h·w). Total O(h·w·log min(h,w))≈700·700·10≈5 million operations, fast enough in C++.

Step by step
- Read h,w and the grid.
- Initialize a rolling-hash object with a random base and precompute base powers up to max(h,w).
- Build for each of the h rows the forward hash h[i][j] and reverse hash rh[i][j].
- Build similarly for each of the w columns the forward and reverse hashes.
- Binary-search the half-size (handling even/odd parity) to find the maximum k for which check(k) returns true.
- In check(k):
  • Loop i from h−1 downto 0, j from w−1 downto 0.
  • If row substring at (i,j) length k is palindrome, then cntDown[i][j]=1+cntDown[i+1][j], else 0.
  • If column substring at (i,j) length k is palindrome, then cntRight[i][j]=1+cntRight[i][j+1], else 0.
  • If both counts ≥k, record success and coordinates.
- After binary search, output the stored best coordinates (converted to 1-based).

Complexity
Time: O((h·w) log (min(h,w))) from binary searches; each check is O(h·w).
Memory: O(h·w) for hashes and count arrays.

3. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/strings/hashing.hpp>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class HashMeta {
  private:
    void set_random_base() {
        seed_seq seed{
            (uint32_t)chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch()
            )
                .count(),
            (uint32_t)random_device()(), (uint32_t)42
        };
        mt19937 rng(seed);
        // base = uniform_int_distribution<uint64_t>(0, mod - 1)(rng);
        base = uniform_int_distribution<uint64_t>()(rng);
    }

    void precompute_base_pow(size_t n) {
        base_pow.resize(n);
        base_pow[0] = 1;
        for(size_t i = 1; i < n; i++) {
            base_pow[i] = mul(base_pow[i - 1], base);
        }
    }

    static constexpr uint64_t add(uint64_t a, uint64_t b) {
        // a += b + 1;
        // a = (a & mod) + (a >> 61);
        // return a - 1;
        return (a + b);
    }

    static constexpr uint64_t sub(uint64_t a, uint64_t b) {
        return a - b;
        // return add(a, mod - b);
    }

    static constexpr uint64_t mul(uint64_t a, uint64_t b) {
        return a * b;
        // uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
        // uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
        // uint64_t ret =
        //     (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
        // ret = (ret & mod) + (ret >> 61);
        // ret = (ret & mod) + (ret >> 61);
        // return ret - 1;
    }

  public:
    class hash_t {
        uint64_t h;

      public:
        hash_t() : h(0) {}
        hash_t(uint64_t h) : h(h) {}
        operator uint64_t() const { return h; }

        hash_t& operator+=(const hash_t& other) {
            h = add(h, other.h);
            return *this;
        }

        hash_t& operator-=(const hash_t& other) {
            h = sub(h, other.h);
            return *this;
        }

        hash_t& operator*=(const hash_t& other) {
            h = mul(h, other.h);
            return *this;
        }

        hash_t operator+(const hash_t& other) const {
            return hash_t(*this) += other;
        }
        hash_t operator-(const hash_t& other) const {
            return hash_t(*this) -= other;
        }
        hash_t operator*(const hash_t& other) const {
            return hash_t(*this) *= other;
        }

        bool operator==(const hash_t& other) const { return h == other.h; }
        bool operator!=(const hash_t& other) const { return h != other.h; }

        // For use in std::map and std::set
        bool operator<(const hash_t& other) const { return h < other.h; }
    };

    uint64_t base;
    vector<hash_t> base_pow;
    // static constexpr uint64_t mod = (1ull << 61) - 1;

    void init(size_t n) {
        set_random_base();
        precompute_base_pow(n);
    }

    template<typename T>
    vector<hash_t> rabin_karp(const T& container) {
        vector<hash_t> h(container.size());
        for(size_t i = 0; i < container.size(); i++) {
            h[i] = (i ? h[i - 1] : hash_t(0)) * hash_t(base) +
                   hash_t(container[i]);
        }
        return h;
    }

    hash_t hash_range(int l, int r, const vector<hash_t>& h) {
        if(l == 0) {
            return h[r];
        }
        return h[r] - h[l - 1] * base_pow[r - l + 1];
    }
};

HashMeta hash_meta;
using hash_t = HashMeta::hash_t;

int n, m;
vector<string> tbl;

void read() {
    cin >> n >> m;
    tbl.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> tbl[i];
    }
}

tuple<bool, pair<int, int>, pair<int, int>> check(
    const vector<vector<hash_t>>& h, const vector<vector<hash_t>>& rh,
    const vector<vector<hash_t>>& v, const vector<vector<hash_t>>& rv, int k
) {
    if(k > n || k > m) {
        return {false, {-1, -1}, {-1, -1}};
    }

    if(k <= 1) {
        return {true, {0, 0}, {0, 0}};
    }

    vector<vector<int>> cnt_right(n, vector<int>(m, 0));
    vector<vector<int>> cnt_down(n, vector<int>(m, 0));
    for(int i = n - 1; i >= 0; i--) {
        for(int j = m - 1; j >= 0; j--) {
            bool is_row_palindrome = false, is_col_palindrome = false;
            if(j + k <= m) {
                hash_t h1 = hash_meta.hash_range(j, j + k - 1, h[i]);
                hash_t rh1 =
                    hash_meta.hash_range(m - 1 - (j + k - 1), m - 1 - j, rh[i]);
                is_row_palindrome = (h1 == rh1);
                cnt_down[i][j] = (int)is_row_palindrome *
                                 (1 + (i + 1 < n ? cnt_down[i + 1][j] : 0));
            }

            if(i + k <= n) {
                hash_t v1 = hash_meta.hash_range(i, i + k - 1, v[j]);
                hash_t rv1 =
                    hash_meta.hash_range(n - 1 - (i + k - 1), n - 1 - i, rv[j]);
                is_col_palindrome = (v1 == rv1);
                cnt_right[i][j] = (int)is_col_palindrome *
                                  (1 + (j + 1 < m ? cnt_right[i][j + 1] : 0));
            }

            if(cnt_right[i][j] >= k && cnt_down[i][j] >= k) {
                return {true, {i, j}, {i + k - 1, j + k - 1}};
            }
        }
    }

    return {false, {-1, -1}, {-1, -1}};
}

void solve() {
    // We look for the largest axis-aligned square in which every row and
    // every column (restricted to the square) is a palindrome.
    //
    // Precompute row hashes h/rh (forward and reversed) and column hashes
    // v/rv, so a length-k substring can be tested for being a palindrome in
    // O(1) by comparing its forward hash with the reversed hash.
    //
    // For a fixed side length k, check() sweeps cells bottom-right to
    // top-left. cnt_down[i][j] counts how many consecutive rows starting at
    // (i, j) have their length-k horizontal slice be a palindrome;
    // cnt_right[i][j] counts how many consecutive columns starting at (i, j)
    // have their length-k vertical slice be a palindrome. A square of side k
    // with top-left (i, j) is valid iff both counters reach k there.
    //
    // The valid side lengths are monotone within a fixed parity (shrinking a
    // valid square keeps it valid), so we binary-search the half-size,
    // probing both parities until one is fixed, and keep the best square.

    hash_meta.init(max(n, m) + 1);
    vector<vector<hash_t>> h(n, vector<hash_t>(m)), rh(n, vector<hash_t>(m));
    for(int i = 0; i < n; i++) {
        h[i] = hash_meta.rabin_karp(tbl[i]);
        rh[i] = hash_meta.rabin_karp(string(tbl[i].rbegin(), tbl[i].rend()));
    }

    vector<vector<hash_t>> v(m, vector<hash_t>(n)), rv(m, vector<hash_t>(n));
    for(int j = 0; j < m; j++) {
        string col;
        for(int i = 0; i < n; i++) {
            col.push_back(tbl[i][j]);
        }
        v[j] = hash_meta.rabin_karp(col);
        rv[j] = hash_meta.rabin_karp(string(col.rbegin(), col.rend()));
    }

    tuple<int, pair<int, int>, pair<int, int>> ans = {-1, {-1, -1}, {-1, -1}};
    int low = (get<0>(ans) + 1) / 2, high = min(n, m) / 2, mid;
    int only_parity = -1;
    while(low <= high) {
        mid = (low + high) / 2;

        int parity = only_parity == -1 ? 1 : only_parity;
        int k = mid * 2 + parity;
        auto [state, p1, p2] = check(h, rh, v, rv, k);
        if(state) {
            ans = max(ans, make_tuple(k, p1, p2));
            low = mid + 1;
        } else {
            if(only_parity == -1) {
                k = mid * 2 + (1 - parity);
                auto [even_state, q1, q2] = check(h, rh, v, rv, k);
                if(even_state) {
                    only_parity = 1 - parity;
                    ans = max(ans, make_tuple(k, q1, q2));
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else {
                high = mid - 1;
            }
        }
    }

    get<1>(ans).first++;
    get<1>(ans).second++;
    get<2>(ans).first++;
    get<2>(ans).second++;

    cout << get<1>(ans) << ' ' << get<2>(ans) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

4. Python Solution with Detailed Comments

```python
import sys
sys.setrecursionlimit(10**7)

def read_input():
    h, w = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(h)]
    return h, w, grid

# We'll use a pair of moduli to reduce collisions
MOD1 = 10**9+7
MOD2 = 10**9+9
BASE = 91138233

def build_hashes(lines, length):
    # Build forward and reverse prefix hashes for each string in 'lines'
    n = len(lines)
    pref = [ [ (0,0) ]*(length+1) for _ in range(n) ]
    rpref = [ [ (0,0) ]*(length+1) for _ in range(n) ]
    for i, s in enumerate(lines):
        h1 = h2 = 0
        rh1 = rh2 = 0
        for j, ch in enumerate(s):
            code = ord(ch) - 96
            h1 = (h1 * BASE + code) % MOD1
            h2 = (h2 * BASE + code) % MOD2
            pref[i][j+1] = (h1, h2)
            rcode = ord(s[-1-j]) - 96
            rh1 = (rh1 * BASE + rcode) % MOD1
            rh2 = (rh2 * BASE + rcode) % MOD2
            rpref[i][j+1] = (rh1, rh2)
    return pref, rpref

def precompute_powers(n):
    # base^0..base^n
    p1 = [1]*(n+1)
    p2 = [1]*(n+1)
    for i in range(n):
        p1[i+1] = p1[i]*BASE % MOD1
        p2[i+1] = p2[i]*BASE % MOD2
    return p1, p2

def get_hash(pref, pows, i, l, r):
    # hash of substring [l..r) in line i
    h1, h2 = pref[i][r]
    g1, g2 = pref[i][l]
    mul1, mul2 = pows[0][r-l], pows[1][r-l]
    return ((h1 - g1*mul1) % MOD1, (h2 - g2*mul2) % MOD2)

def find_square(h, w, grid):
    # Precompute row hashes
    row_pref, row_rpref = build_hashes(grid, w)
    # Precompute column strings
    cols = [''.join(grid[i][j] for i in range(h)) for j in range(w)]
    col_pref, col_rpref = build_hashes(cols, h)

    pows = precompute_powers(max(h,w)+1)
    best = (0, 0, 0, 0, 0)  # (size, r1, c1, r2, c2)

    def check(k):
        # cnt_down[i][j]: number of consecutive palindrome rows of length k from row i downward at column j
        # cnt_right[i][j]: number of consecutive palindrome columns of length k from col j rightward at row i
        cnt_down = [[0]*w for _ in range(h)]
        cnt_right= [[0]*w for _ in range(h)]
        for i in range(h-1, -1, -1):
            for j in range(w-1, -1, -1):
                # check row palindrome at (i,j)
                if j+k <= w:
                    hf = get_hash(row_pref, pows, i, j, j+k)
                    hr = get_hash(row_rpref,pows, i, w-(j+k), w-j)
                    if hf == hr:
                        cnt_down[i][j] = 1 + (cnt_down[i+1][j] if i+1<h else 0)
                # check column palindrome at (i,j)
                if i+k <= h:
                    vf = get_hash(col_pref, pows, j, i, i+k)
                    vr = get_hash(col_rpref,pows, j, h-(i+k), h-i)
                    if vf == vr:
                        cnt_right[i][j] = 1 + (cnt_right[i][j+1] if j+1<w else 0)
                # if we have k rows and k columns
                if cnt_down[i][j] >= k and cnt_right[i][j] >= k:
                    return (i, j)
        return None

    # Binary search on k from 1..min(h,w)
    lo, hi = 1, min(h,w)
    while lo <= hi:
        mid = (lo+hi)//2
        pos = check(mid)
        if pos:
            # found size mid
            best = (mid, pos[0], pos[1])
            lo = mid+1
        else:
            hi = mid-1

    k, i, j = best
    return (i+1, j+1, i+k, j+k)

def main():
    h, w, grid = read_input()
    r1, c1, r2, c2 = find_square(h, w, grid)
    print(r1, c1, r2, c2)

if __name__ == "__main__":
    main()
```

5. Compressed Editorial

1. Precompute forward/reverse rolling hashes for all rows and all columns in O(h·w).
2. Binary-search the maximum square size k (using half-size with both parity probes to handle even/odd k).
3. For each candidate k, in O(h·w) check every top-left: use two DP arrays (`cnt_down`, `cnt_right`) to ensure k consecutive palindrome rows and columns.
4. Total time O(h·w·log min(h,w)), fast for h,w≤700.
