struct SparseTable
{
    int st[2][MAXN][MAXN][7][7];
    void build()
    {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                st[0][i][j][0][0] = a[i][j] - 'a' + 1;
        for (int i1 = n - 1, i = 0; i1 >= 0; --i1, ++i)
            for (int j1 = m - 1, j = 0; j1 >= 0; --j1, ++j)
                st[1][i][j][0][0] = a[i1][j1] - 'a' + 1;
        for (int id = 0; id < 2; ++id)
        {
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < m; ++j)
                {
                    for (int lg = 1; lg <= lgs[n]; ++lg)
                    {
                        st[id][i][j][0][lg] = (mul(st[id][i][j][0][lg - 1], q[1 << (lg - 1)]) + st[id][i][j + (1 << (lg - 1))][0][lg - 1]) % HMOD;
                    }
                }
            }
            for (int lg = 1; lg <= lgs[n]; ++lg)
            {
                for (int i = 0; i < n; ++i)
                {
                    for (int lg1 = 1; lg1 <= lgs[m]; ++lg1)
                    {
                        for (int j = 0; j < m; ++j)
                        {
                            st[id][i][j][lg][lg1] = (mul(st[id][i][j][lg - 1][lg1], p[1 << (lg - 1)]) + st[id][i + (1 << (lg - 1))][j][lg - 1][lg1]) % HMOD;
                        }
                    }
                }
            }
        }
    }
    int check(int x1, int y1, int x2, int y2)
    {
        int nx1 = n - 1 - x2, ny1 = m - 1 - y2, nx2 = n - 1 - x1, ny2 = m - 1 - y1;
        int ans = 0;
        int k1 = lgs[x2 - x1 + 1];
        int k2 = lgs[y2 - y1 + 1];
        ans += st[0][x1][y1][k1][k2] == st[1][nx1][ny1][k1][k2];
        ans += st[0][x2 - (1 << k1) + 1][y1][k1][k2] == st[1][nx2 - (1 << k1) + 1][ny1][k1][k2];
        ans += st[0][x1][y2 - (1 << k2) + 1][k1][k2] == st[1][nx1][ny2 - (1 << k2) + 1][k1][k2];
        ans += st[0][x2 - (1 << k1) + 1][y2 - (1 << k2) + 1][k1][k2] == st[1][nx2 - (1 << k1) + 1][ny2 - (1 << k2) + 1][k1][k2];
        return ans == 4;
    }
} T;