package q2975

import "slices"

func maximizeSquareArea(m int, n int, hFences []int, vFences []int) int {
	slices.Sort(hFences)
	slices.Sort(vFences)
	nHFences := len(hFences) + 2

	lengths := make(map[int]struct{}, nHFences*(nHFences-1)/2)
	for i := -1; i < len(hFences); i++ {
		a := 1
		if i >= 0 {
			a = hFences[i]
		}
		for j := i + 1; j <= len(hFences); j++ {
			b := m
			if j < len(hFences) {
				b = hFences[j]
			}
			lengths[b-a] = struct{}{}
		}
	}

	maxEdge := -1
	for i := -1; i < len(vFences); i++ {
		a := 1
		if i >= 0 {
			a = vFences[i]
		}
		for j := i + 1; j <= len(vFences); j++ {
			b := n
			if j < len(vFences) {
				b = vFences[j]
			}

			if _, ok := lengths[b-a]; ok {
				maxEdge = max(maxEdge, b-a)
			}
		}
	}
	if maxEdge == -1 {
		return -1
	}

	maxEdge %= 1e9 + 7
	return (maxEdge * maxEdge) % (1e9 + 7)
}

var _ = maximizeSquareArea