<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

504. Square Palindrome
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Andrew has just made a breakthrough in computer science: he realized how to quickly find the largest palindrome square on a given rectangle of letters. Can you do the same? A square consisting of n rows of n letters each is a palindrome square of size n if each row and each column of this square is a palindrome string. A string is a palindrome string if its first letter is the same as its last letter, its second letter is the same as its next-to-last letter, and so on.
Input
The first line of the input file contains two integers h and w (1 ≤ h,w ≤ 700) — the height and width of the given rectangle of letters. The next h lines contain w lowercase English letters each — the given rectangle of letters itself.
Output
Output the coordinates of the largest palindrome square that is a part of the given rectangle of letters. Output four integers: the first row of the square, the first column of the square, the last row of the square, the last column of the square. The rows are numbered from 1 to h, the columns are numbered from 1 to w. If there are several solutions, output any.
Example(s)
sample input
sample output
5 10
abccbfghij
abccbfghij
abccbfghij
abccbfghij
abcdefghij
1 2 4 5

<|response|>
1. Abridged problem statement
Given an h×w grid of lowercase letters (1≤h,w≤700), find the largest k×k sub-square such that every row of that sub-square is a palindrome and every column of that sub-square is a palindrome. Output any one such square by its 1-based coordinates (r1, c1, r2, c2).

2. Key observations
- Checking whether an arbitrary substring is a palindrome can be done in O(1) after O(n) preprocessing via rolling hashes (compute forward and reverse prefix-hashes).
- For a fixed size k, define two boolean grids:
  • rowPal[i][j] = true if in row i, the substring from column j to j+k−1 is a palindrome.
  • colPal[i][j] = true if in column j, the substring from row i to i+k−1 is a palindrome.
- We need a k×k square whose top-left corner is (i,j) such that:
  • For all t=0…k−1, rowPal[i+t][j] is true (k consecutive palindrome rows starting at i).
  • For all t=0…k−1, colPal[i][j+t] is true (k consecutive palindrome columns starting at j).
- We can speed up that "all k in a row" check by dynamic programming on cntDown and cntRight:
  • cntDown[i][j] = 1 + cntDown[i+1][j] if rowPal[i][j] else 0.
  • cntRight[i][j] = 1 + cntRight[i][j+1] if colPal[i][j] else 0.
  Then (i,j) is valid if cntDown[i][j]≥k and cntRight[i][j]≥k.
- Binary-search k: valid sizes are monotone within each parity (even/odd), so we binary-search the half-size and probe both parities until one is fixed. Each check is O(h·w). Total O(h·w·log (min(h,w))).

3. Full solution approach
a. Read h, w and the grid.
b. Pick a random 64-bit base and precompute base powers up to max(h,w).
c. For each row, build two prefix-hash arrays: forward and reversed.
d. For each column (treating it as a string of length h), build its forward and reversed prefix hashes.
e. Define a function check(k) that:
   - Builds cntDown and cntRight by scanning i=n−1…0, j=m−1…0:
     • Use the rolling hashes of row i and its reverse to see if substring [j…j+k−1] is palindrome → set cntDown[i][j].
     • Use the column hashes at column j to see if substring [i…i+k−1] is palindrome → set cntRight[i][j].
     • If cntDown[i][j]≥k and cntRight[i][j]≥k, record (i,j) and return true.
   - If none found, return false.
f. Binary-search the half-size, probing both parities until one is determined, storing the best square found.
g. Print the stored coordinates in 1-based indexing.

4. C++ implementation with detailed comments
```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;
}
```

5. Python implementation 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)

    def check(k):
        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:
            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()
```

Explanation of the Python code:
- We precompute double rolling hashes for all rows and columns (forward and reverse).
- The function `check(k)` computes two DP tables (`cntDown` and `cntRight`) bottom-up, testing palindromicity in O(1) per substring via the hashes.
- Binary search finds the maximum k for which `check(k)` succeeds, and we output its 1-based square coordinates.
