C. Chess in 3D
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the mystical kingdom of TriDChess, the ancient game of chess has evolved into a thrilling three—dimensional contest of strategy and intellect. The game is played on a board with dimensions $$$A \times B \times C$$$, where each of the three axes represents a spatial dimension. This board forms a cuboid, filled with possibilities for cunning moves and strategic placements.

The piece of focus in this game is the 3D Knight, a nimble entity that combines the powers of traditional chess knights with the freedom of movement afforded by the third dimension. These 3D Knights have the ability to move in an L—shape across the board, jumping over other pieces. Their movement is defined as follows:

1. L—Shaped Movement: A 3D Knight can move in an L—shape from its current position $$$(x, y, z)$$$:

  • Move two squares along one axis and one square along another axis:

  • $$$(x \pm 2, y \pm 1, z)$$$, $$$(x \pm 2, y, z \pm 1)$$$, $$$(x \pm 1, y \pm 2, z)$$$, $$$(x, y \pm 2, z \pm 1)$$$, $$$(x \pm 1, y, z \pm 2)$$$, $$$(x, y \pm 1, z \pm 2)$$$.

2. The Knight's jump allows it to move over other pieces, but it must land within the bounds of the board, where $$$1 \leq x \leq A$$$, $$$1 \leq y \leq B$$$, $$$1 \leq z \leq C$$$.

Additionally, there are between 1 and 500 blocked cells on the board where Knights cannot be placed. These cells are specified by their coordinates and must be avoided when placing Knights.

The challenge you face is to determine the maximum number of these agile 3D Knights that can be placed on the cuboid board such that no two Knights are capable of attacking each other. This means no two Knights should be in a position where one could reach the other in a single move.

Input

The first line contains three integers $$$A$$$, $$$B$$$, and $$$C$$$ ($$$1 \leq A, B, C \leq 10$$$), representing the dimensions of the 3D board.

The second line contains an integer $$$K$$$ ($$$1 \leq K \leq 500$$$), representing the number of blocked cells.

The next $$$K$$$ lines each contain three integers $$$x, y, z$$$ ($$$1 \leq x \leq A$$$, $$$1 \leq y \leq B$$$, $$$1 \leq z \leq C$$$), representing the coordinates of a blocked cell.

Output

Output a single integer that represents the maximum number of 3D Knights that can be positioned on the $$$A \times B \times C$$$ board without any two Knights threatening one another.

Example
Input
3 3 3
1
2 2 2
Output
14