class Solution:
    '''
    Time Complexity: O(h^2 + v^2)
    Space Complexity: O(h^2 + v^2). Actual: O(min(m + n, h^2 + v^2))
    Where, h is number of horizontal fences, v is number of vertical fences (including boundaries 1 and m/n).
    The key insight is that we can only make a square of side S,
    if there exists a horizontal fence at distance S from some other horizontal fence,
    and similarly for vertical fences.
    So we generate all possible horizontal distances and store in a set.
    Then we generate all possible vertical distances and check if it exists in horizontal distances set.
    Return the largest such distance.
    '''
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        # Include boundary fences
        h = sorted([1] + hFences + [m])
        v = sorted([1] + vFences + [n])

        # All possible horizontal distances
        h_dist = set()
        for i in range(len(h)):
            for j in range(i + 1, len(h)):
                h_dist.add(h[j] - h[i])

        # All possible vertical distances
        v_dist = set()
        for i in range(len(v)):
            for j in range(i + 1, len(v)):
                v_dist.add(v[j] - v[i])

        # Find largest common distance
        common = h_dist & v_dist
        if not common:
            return -1

        max_side = max(common)
        return (max_side * max_side) % (10**9 + 7)