Этажи
Новая автомагистраль обещала лучшее и более быстрое соединение между A и B, а также значительное уменьшение заторов. Однако возникло препятствие: старинный особняк. Этот конфликт вскоре был разрешен в пользу автомагистрали.
Незадолго до начала сноса особняка, любитель старинных зданий обнаружил, что красочно выложенные плиточные полы в особняке были спроектированы знаменитым художником Мондрианом и, следовательно, имели большую культурную ценность. Их следовало сохранить и удалить из особняка до его сноса.
Для выполнения этой задачи был нанят эксперт по перемещению полов. Он решил разрезать каждый пол на более мелкие части, чтобы сделать его более управляемым. У него был отличный инструмент для резки полов, который позволял разрезать прямоугольный кусок пола на два меньших прямоугольных куска, разрезая параллельно одной из сторон. Конечно, резка должна была проходить между плитками; резать через плитку было невозможно. Таким образом, пол на Рисунке 1 можно было легко разрезать на 9 плиток. Пол на Рисунке 2, однако, нельзя разрезать на более мелкие части. Пол на Рисунке 3 можно разрезать на шесть частей, но одна из частей будет состоять из нескольких плиток.
Готовясь к работе, эксперт по перемещению полов был обеспокоен тем, насколько большими могут быть оставшиеся части: будут ли они тяжелыми, очень тяжелыми или чрезвычайно тяжелыми? Какой инструмент для подъема полов следует нанять? Поскольку полы имеют фиксированную толщину и плотность, вес куска пола зависит только от его площади.
Дан прямоугольный пол, покрытый прямоугольными плитками. Необходимо найти площадь самого большого куска после того, как пол будет разрезан на наименьшие возможные куски. Слова "наименьшие" и "самые большие" относятся к площади кусков. Резка через плитку не допускается. Разрез через прямоугольник всегда параллелен одной из сторон и проходит через всю длину (или ширину) прямоугольника.
Входные данные
Входные данные содержат несколько полов. Первая строка входных данных указывает количество полов.
Каждый пол описывается в нескольких строках. Первая строка содержит два положительных целых числа: длину и ширину пола в миллиметрах. Пол имеет длину или ширину не более 40 000 мм. Следующая строка содержит одно число: количество плиток t (1 ≤ t ≤ 100). Следующие t строк содержат описание плитки. Плитка задается четырьмя целыми числами: xl yl xh yh, где (xl, yl) — координаты нижнего левого угла плитки, а (xh, yh) — координаты верхнего правого угла плитки. Плитка всегда имеет положительную площадь. Порядок координат пола и плитки, конечно, совпадает.
Вы можете предположить, что плитки не пересекаются и покрывают весь пол, и только пол.
Выходные данные
Для каждого тестового случая (каждого пола) выводите число в одной строке: площадь самого большого куска пола (в квадратных миллиметрах) после разрезания пола на наименьшие возможные куски с учетом данных ограничений.