Problem B
Breaking 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.

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