 ICPC Vietnam National Programming Contest 2019

#### Start

2019-11-02 17:00 AKDT

## ICPC Vietnam National Programming Contest 2019

#### End

2019-11-02 22:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -722 days 12:11:19

5:00:00

0:00:00

# Problem BBreaking Cake

The Hunter Exam has begun!

The first round of the Hunter Exam is a real-life problem solving test: Each candidate is given a rectangular parallelepiped cake of size $a \times b \times c$, which can be divided into unit cubes of size $1 \times 1 \times 1$.

Inside the cake, there are $m$ unit cubes containing chocolate chips. The $i$-th cube is located at position $(x_ i, y_ i, z_ i)$.

The candidates must divide their given cake into exactly $m$ rectangular parallelepiped parts, satisfying all the following conditions:

• For every two parts, their common space’s volume must be zero.

• Each part must contain exactly one chocolate chip.

• The coordinates of the corners of all $m$ parts must be integers.

• To prevent wasted food, candidates cannot throw away any part of the cake.

Can you divide the cake satisfying all the constraints and pass the first round of the Hunter Exam?

## Input

The input contains multiple test cases. Each test case is described as below:

• The first line contains exactly $4$ positive integers $a$, $b$, $c$ and $m$. $(1 \le a, b, c \le 10^6, 1 \le m \le 10^3)$.

• In the next $m$ lines, the $i$-th line contains exactly $3$ positive integers $x_ i$, $y_ i$ and $z_ i$ — the coordinates of the $i$-th chocolate chip. No two chips are in the same position. $(1 \le x_ i \le a, 1 \le y_ i \le b, 1 \le z_ i \le c)$.

Sum of $m$ over all test cases in one input file is at most $5 \times 10^4$.

The last line of the input contains a single number $-1$.

## Output

For each test case:

• If it is impossible to divide the cake satisfying the above constraints, print exactly one line containing ‘NO’ .

• Otherwise, output one line containing ‘YES’, followed by $m$ lines. The $i+1$-th line $(1 \le i \le m)$ contains exactly $6$ integers, $x_ i$, $y_ i$, $z_ i$, $u_ i$, $v_ i$ and $w_ i$ representing the $i$-th part $(1 \le x_ i \le u_ i \le a, 1 \le y_ i \le v_ i \le b, 1 \le z_ i \le w_ i \le c)$. $(x_ i, y_ i, z_ i)$ and $(u_ i, v_ i, w_ i)$ are the coordinates of two opposite unit cubes of the $i$-th part. The $i$-th part must contain the $i$-th chocolate chip.

Sample Input 1 Sample Output 1
5 5 5 2
1 1 1
5 5 5
5 5 5 1
3 3 3
-1

YES
1 1 1 5 5 1
1 1 2 5 5 5
YES
1 1 1 5 5 5