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