거대한 덮개

뤼트여브룩 공과대학교의 한 학생이 캠퍼스의 건물을 모두 반투명 플라스틱 덮개 하나로 덮으려고 한다. 그러면 이 일대에서 우산을 쓸 일이 없어져 비용이 크게 줄어든다.

덮개 값은 넓이에 비례하므로 학생은 넓이가 가장 작은 덮개를 원한다. 그 최소 넓이를 계산하는 프로그램을 작성하라.

캠퍼스 부지는 평평한 직사각형이다. 건물은 모두 지면 위에 놓인 직육면체의 합집합이고, 직육면체끼리 겹칠 수 있다. 덮개는 건물을 남김없이 덮어야 하며 캠퍼스의 네 변에 지면 높이로 고정된다.

덮개는 팽팽하게 당겨져 있다. 즉 덮개와 지면이 둘러싸는 입체는 볼록하다. 이 조건을 만족하는 덮개 중에서 넓이가 가장 작은 것의 넓이를 구하라. 지면 직사각형 자체는 넓이에 포함하지 않는다.

첫 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 공백으로 구분된 정수 네 개 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. 캠퍼스 부지는 $[x_1, x_2] \times [y_1, y_2]$이고, $-10^4 \le x_1 < x_2 \le 10^4$, $-10^4 \le y_1 < y_2 \le 10^4$이다.
• 다음 줄에 건물을 이루는 직육면체의 개수 $n$이 주어진다. $0 \le n \le 400$이다.
• 이어지는 $n$개 줄 가운데 $i$번째 줄에 공백으로 구분된 정수 다섯 개 $a_i$, $b_i$, $c_i$, $d_i$, $h_i$가 주어진다. 밑면이 $[a_i, c_i] \times [b_i, d_i]$이고 높이가 $h_i$인 직육면체를 뜻한다. $x_1 \le a_i < c_i \le x_2$, $y_1 \le b_i < d_i \le y_2$, $0 < h_i \le 10^4$이다.

여기서 $[a, c] \times [b, d]$는 데카르트 곱이며, $a \le x \le c$이고 $b \le y \le d$인 점 $(x, y)$ 전체가 이루는 직사각형 영역이다.

각 테스트 케이스마다 최소 덮개의 넓이를 소수점 아래 넷째 자리까지 한 줄에 출력한다. 반올림은 통상적인 방식을 따른다. 버릴 자리의 첫 숫자가 5 이상이면 올리고, 그렇지 않으면 내린다.