박스 아트

정육면체 조각으로 세계적으로 유명한 예술가 A.A. Blox는 투명한 아크릴 유리 직육면체로 인상적인 작품을 만드는 완전히 새로운 방법을 개발했다. 친구 T.D. Resal이 만든 특허 레이저 장치를 사용하면, 원래 무색이던 직육면체의 일부분 색을 바꿀 수 있다. 다만 이 레이저 장치는 아직 시제품이라, 큰 직육면체의 면과 평행한 면을 가진 직육면체 영역("축에 정렬된" 영역)만 색칠할 수 있다.

완성된 작품의 가치는 색칠된 아크릴 유리의 부피로 측정된다. A.A. Blox는 수학에 능숙하지 않아, 작품의 가격을 대신 계산해 줄 당신을 고용했다.

축에 정렬된 초기 직육면체 $b$와 축에 정렬된 직육면체들의 집합 $S$가 주어질 때, $S$에 속한 직육면체들 중 $b$ 안에 들어가는 부분들의 합집합 부피를 구하라. 여러 직육면체가 겹치는 부분의 부피는 한 번만 세어야 한다.

첫 번째 줄에는 시나리오의 수가 주어진다.

각 시나리오는 초기 직육면체 $b$의 두 대각 꼭짓점 $(x_1, y_1, z_1)$과 $(x_2, y_2, z_2)$를 나타내는 x1 y1 z1 x2 y2 z2 형식의 줄로 시작한다. 모든 수는 하나의 공백으로 구분된다.

그다음 줄에는 레이저 장치로 색칠된 집합 $S$의 직육면체 개수 $m$ ($m \le 2000$)이 주어지고, 이어서 $m$개의 줄에 각각 하나의 직육면체의 두 대각 꼭짓점을 나타내는 x1 y1 z1 x2 y2 z2가 주어진다.

모든 좌표는 $0$부터 $1000$까지의 정수이며, 각 줄은 $x_1 \le x_2$, $y_1 \le y_2$, $z_1 \le z_2$를 만족한다.

각 시나리오마다 먼저 Scenario #i: 형식의 줄을 출력한다. 여기서 $i$는 $1$부터 시작하는 시나리오 번호이다. 그다음 줄에 색칠된 아크릴 유리의 총 부피를 출력한다. 연속한 시나리오 사이는 빈 줄로 구분한다.