바닥재 자르기

새 고속도로는 A와 B를 더 빠르고 원활하게 연결하고 정체를 크게 줄여 줄 것으로 기대되었다. 그러나 오래된 저택이라는 장애물이 있었고, 이 갈등은 곧 고속도로 쪽으로 결론이 났다.

저택 철거가 시작되기 직전, 오래된 저택을 사랑하는 한 사람이 저택의 화려한 타일 바닥이 유명한 화가 몬드리안이 디자인한 것으로 큰 문화적 가치가 있음을 알게 되었다. 이 바닥은 저택이 철거되기 전에 반드시 보존되어, 저택에서 떼어내야 했다.

바닥을 옮기는 전문가가 고용되었다. 그는 작업을 다루기 쉽게 하기 위해 각 바닥을 더 작은 조각으로 자르기로 했다. 그가 가진 정교한 절단 도구는 직사각형 바닥 조각을 한 변에 평행하게 잘라 두 개의 더 작은 직사각형 조각으로 나눌 수 있었다. 물론 자르기는 타일과 타일 사이에서만 이루어져야 하며, 타일을 관통해 자르는 것은 허용되지 않는다. 이런 방식으로 그림 1의 바닥은 9개의 타일로 쉽게 나눌 수 있다. 반면 그림 2의 바닥은 더 작은 조각으로 나눌 수 없다. 그림 3의 바닥은 여섯 조각으로 나눌 수 있지만, 그중 한 조각은 여러 개의 타일로 이루어진다.

전문가는 남는 조각들이 얼마나 무거울지 궁금했다. 바닥의 두께와 밀도가 일정하므로 조각의 무게는 오직 넓이에만 의존한다.

직사각형 타일들로 덮인 직사각형 바닥이 주어진다. 규칙에 따라 바닥을 더 이상 자를 수 없을 때까지 최대한 잘게 자른 뒤, 그 결과로 생긴 조각들 중 가장 큰 조각의 넓이를 구하라. 여기서 '가장 작은'과 '가장 큰'은 조각의 넓이를 뜻한다. 타일을 관통해 자르는 것은 허용되지 않으며, 자르기는 항상 직사각형의 한 변에 평행하고 그 전체 길이(또는 너비)를 가로지른다.

입력은 여러 개의 바닥으로 이루어진다. 첫 줄에는 바닥의 개수가 주어진다.

각 바닥은 여러 줄로 기술된다. 첫 줄에는 바닥의 길이와 너비가 밀리미터 단위의 두 양의 정수로 주어진다. 바닥의 길이와 너비는 각각 최대 $40000$ mm이다. 다음 줄에는 타일의 개수 $t$ ($1 \le t \le 100$)가 주어진다. 이어지는 $t$개의 줄에는 각각 하나의 타일이 네 정수로 주어진다:

xl yl xh yh

여기서 $(x_l, y_l)$은 타일의 왼쪽 아래 모서리, $(x_h, y_h)$는 타일의 오른쪽 위 모서리의 좌표이다. 모든 타일의 넓이는 양수이다. 바닥과 타일의 좌표 축 방향은 서로 일치한다. 타일들은 서로 겹치지 않으며, 바닥 전체를 빈틈없이 정확히 덮는다.

각 바닥(각 테스트 케이스)마다, 주어진 제약에 따라 바닥을 가능한 한 가장 작은 조각들로 자른 뒤 가장 큰 조각의 넓이(제곱 밀리미터)를 한 줄에 하나씩 출력한다.