Problem C
Checking Break

As you already know from the previous problem, ‘Breaking Cake’, the first round of the Hunter Exam has begun.

The following paragraphs are copied from the problem statement of ‘Breaking Cake’:

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 \cdot b \cdot c$, which can be divided into unit cubes of size $1 \cdot 1 \cdot 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?

This year, $10^9 + 7$ candidates participated in the first round of the Hunter Exam! Obviously, it is impossible for the Hunter Exam organizers, the Hunter Association, to manually check all the candidates’ solutions. As the only programmer of the Hunter Association, you have been tasked with writing a program to automatically check whether the candidates’ solutions are valid.

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 $(1 \le x_ i \le a, 1 \le y_ i \le b, 1 \le z_ i \le c)$. No two chips are in the same position.

• The next $m$ lines describe a solution given by a candidate:

  • The $i$-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, u_ i, y_ i, v_ i, z_ i, w_ i \le 10^6)$. $(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.

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

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

Output

For each test case, print exactly one line, containing ‘YES’ if the candidate’s solution satisfies all the given constraints:

• The $i$-th part must contains the $i$-th chocolate chip.

• Candidate did not throw away any part of the cake.

• The volume of the intersection of any two parts must be equal to zero.

• $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$.

Otherwise, print ‘NO’.

Note that it is not guaranteed that the cake can be divided into $m$ parts satisfying all the given constraints. In which case, the output for that test case would be ‘NO’.

5 5 5 2
1 1 1
5 5 5
1 1 1 5 5 1
1 1 2 5 5 5
5 5 5 1
3 3 3
1 1 1 5 5 6
-1

YES
NO