슬라이싱 트리

VLSI 회로는 오늘날 수백만 개의 트랜지스터에 이를 만큼 복잡해서, CAD 도구 없이 설계하기가 사실상 불가능합니다. 설계 과정의 복잡도를 낮추기 위해 전체 과정은 여러 중간 단계로 나뉘며, 그중 하나가 물리 설계(physical design) 단계입니다. 물리 설계 단계에서 회로의 기본 구성 요소는 보통 직사각형 모듈로 다룹니다. 이 단계 안에서도 여러 세부 단계가 있는데, 회로 성능에 가장 결정적인 것이 배치(floorplan/placement) 단계입니다. 실제 VLSI 배치 문제는 매우 복잡하지만, 여기서는 각 구성 요소를 평면 위의 직사각형 하나로 보는 단순화된 형태만 다룹니다.

단순화된 배치 문제는, 주어진 제약을 만족하도록 $n$개의 직사각형을 축에 평행한 방향으로 평면에 놓는 것입니다. 직사각형들 사이의 상대적 위치가 제약으로 주어집니다. 상대적 위치란, 직사각형 $R_i$ ($1 \le i \le n$)를 직사각형 $R_j$ ($1 \le j \le n$)의 아래(또는 위)에 놓거나, 왼쪽(또는 오른쪽)에 놓아야 한다는 뜻입니다. 각 직사각형 $R_i$의 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표를 각각 $(x_i^{ll}, y_i^{ll})$, $(x_i^{ur}, y_i^{ur})$로 표기합니다. $R_i$가 $R_j$의 아래에 놓인다는 것은 $y_i^{ur} \le y_j^{ll}$을 뜻하고, 마찬가지로 $R_i$가 $R_j$의 왼쪽에 놓인다는 것은 $x_i^{ur} \le x_j^{ll}$을 뜻합니다. 각 직사각형은 $90^\circ$ 회전하여 놓을 수도 있습니다. 참고로 "$R_1$이 $R_2$의 아래"라는 하나의 제약도 여러 가지 배치로 만족시킬 수 있습니다.

직사각형들 사이의 상대적 위치 제약은 슬라이싱 트리(slicing tree)라 부르는 이진 트리로 표현합니다. 슬라이싱 트리는 평면이 어떻게 분할되고 각 부분 영역에 어떤 직사각형이 놓이는지를 나타냅니다. 트리의 각 내부 노드에는 $H$ 또는 $V$라는 표시가 붙고, 각 외부 노드(잎)에는 직사각형 번호 $i$ ($1 \le i \le n$)가 붙습니다. 내부 노드의 표시 $H$는 그 부분 영역이 수평선으로 분할됨을, $V$는 수직선으로 분할됨을 뜻합니다. 예를 들어 잎이 둘뿐인 트리에서 뿌리가 $H$이면 $R_1$을 $R_2$의 아래에 놓으라는 뜻이고, 뿌리가 $V$이면 $R_1$을 $R_2$의 왼쪽에 놓으라는 뜻입니다.

일반적으로, 어떤 내부 노드 $N_k$의 표시가 $H$이면 $N_k$의 왼쪽 부분 트리에 속한 모든 직사각형은 오른쪽 부분 트리에 속한 모든 직사각형보다 아래에 놓여야 합니다. 마찬가지로 $N_k$의 표시가 $V$이면 왼쪽 부분 트리의 모든 직사각형은 오른쪽 부분 트리의 모든 직사각형보다 왼쪽에 놓여야 합니다.

어떤 배치가 정해졌을 때 그 배치의 모든 직사각형을 감싸는 최소 직사각형을 $\boxed{R}$라 하겠습니다. 슬라이싱 트리와 각 직사각형의 크기가 주어졌을 때, 제약을 모두 만족하면서 감싸는 직사각형 $\boxed{R}$의 넓이가 가능한 한 작아지도록 각 직사각형의 위치(와 방향)를 정하는 프로그램을 작성하세요. $\boxed{R}$의 넓이는 각 직사각형의 방향에 따라 달라질 수 있음에 유의하세요.

입력은 표준 입력으로 주어집니다. 입력은 $T$개의 테스트 케이스로 이루어지며, 첫 줄에 테스트 케이스의 수 $T$가 주어집니다.

각 테스트 케이스의 첫 줄에는 직사각형의 개수 $n$ ($1 \le n \le 1000$)이 주어집니다. 이어지는 $n$개의 줄에는 각 직사각형의 크기가 한 줄에 하나씩 주어집니다. $i$번째 줄($1 \le i \le n$)에는 직사각형 $i$의 너비 $w$와 높이 $h$를 나타내는 두 정수 $w$, $h$ ($1 \le w, h \le 500$)가 주어집니다.

그다음 줄에는 슬라이싱 트리 정보가 주어집니다. 이 정보는 트리를 후위 순회(post-order)하여 얻은, 공백으로 구분된 $2n - 1$개의 항목으로 이루어진 목록입니다. 각 항목은 내부 노드 표시이거나 외부 노드(잎) 표시입니다. 내부 노드의 표시는 $H$ 또는 $V$이고, 외부 노드의 표시는 직사각형 번호를 나타내는 정수 $i$ ($1 \le i \le n$)입니다.

출력은 표준 출력으로 합니다. 각 테스트 케이스마다 정확히 한 줄을 출력합니다. 각 테스트 케이스에 대해, 직사각형들 사이의 상대적 위치 제약을 모두 만족하면서 감싸는 직사각형 $\boxed{R}$의 넓이가 최소가 되는 배치를 찾은 뒤, 그 최소 넓이를 한 줄에 출력하세요. 모든 테스트 케이스에서 $\boxed{R}$의 넓이는 $10^{10}$보다 작다고 가정해도 됩니다.