K. 3D Turf War
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a four-dimensional world, video games would take place on three-dimensional screens in the same way we humans play video games on two-dimensional screens. There are $$$k$$$ four-dimensional beings playing their favorite game on an $$$m \times n \times h$$$ grid. Each player has their own color.

The game has $$$r$$$ turns. Each turn results in some player coloring a rectangular prism subgrid with their color. If any of these cells had been previously colored, they are overwritten to have the new color.

Formally, a turn is defined by a player number $$$i$$$ and two triples $$$(x_1, y_1, z_1)$$$ and $$$(x_2, y_2, z_2)$$$, where $$$x_1 \le x_2$$$; $$$y_1 \le y_2$$$; and $$$z_1 \le z_2$$$. Player $$$i$$$ colors all $$$(x, y, z)$$$ such that $$$x_1 \le x \le x_2$$$; $$$y_1 \le y \le y_2$$$; and $$$z_1 \le z \le z_2$$$. Below is an example of a turn for $$$m = 4, n = 3, h = 2$$$. The player has colored the subgrid defined by corners $$$(0, 0, 0)$$$ and $$$(2, 1, 1)$$$.

Your task is to calculate, at the end of the game, how many cells in the grid were only ever colored by one player. Note that a cell might get colored by the same player multiple times across different turns.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50$$$). The description of the test cases follows.

The first line of each test case consists of five integers, $$$m$$$, $$$n$$$, $$$h$$$, $$$k$$$ and $$$r$$$ ($$$1 \le mnh, k, r \le 4 \cdot 10^5$$$) — this represents a $$$k$$$-player game lasting $$$r$$$ turns played on an $$$m \times n \times h$$$ grid.

The next $$$r$$$ lines of each test case consist of seven integers each: $$$i, x_1, y_1, z_1, x_2, y_2, z_2$$$ ($$$0 \le i, x_1, y_1, z_1, x_2, y_2, z_2 \lt 4 \cdot 10^5$$$). The following conditions are guaranteed: $$$i \lt k$$$; $$$x_1 \le x_2 \lt m$$$; $$$y_1 \le y_2 \lt n$$$; and $$$z_1 \le z_2 \lt h$$$. This line represents a turn in which player number $$$i$$$ colors the entire subgrid defined by $$$(x_1, y_1, z_1)$$$ and $$$(x_2, y_2, z_2)$$$.

It is guaranteed that the sum of $$$mnh$$$ over all test cases is at most $$$4 \cdot 10^5$$$ and the sum of $$$r$$$ over all test cases is at most $$$4 \cdot 10^5$$$.

Output

For each test case, output a single integer — the number of cells in the grid that were only ever colored by exactly one player.

Example
Input
3
4 3 2 2 3
0 0 0 0 2 1 1
1 1 0 0 1 2 1
0 0 1 0 2 2 0
2 2 1 4 4
0 0 0 0 0 0 0
1 0 1 0 0 1 0
2 1 0 0 1 0 0
3 1 1 0 1 1 0
1 2 2 3 3
0 0 0 0 0 1 1
1 0 0 0 0 0 1
2 0 1 0 0 1 1
Output
11
4
0
Note

In the first test case, there are two players and three turns. Here are the game states after each turn.

The changes to the state after the third move are not visible from the previous angle, so a rotated view is below.
In total, 16 cells were colored over the course of the game. Of these, the five cells $$$\{(1, 0, 0), (1, 1, 0), (1, 2, 0), (1, 0, 1), (1, 1, 1)\}$$$ were colored by both players at some point. The other 11 were only touched by one player (10 by the first player and 1 by the second player).