L. Architect
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Steve, a professional architect, is working on a project where he needs to assemble $$$n$$$ cuboid building blocks to form a larger cuboid structure, with no overlapping among the small cuboids and no gaps left unfilled within the large cuboid. The lower left corner of the larger cuboid structure should be at $$$(0,0,0)$$$, and the upper right corner should be at $$$(W,H,L)$$$. Before starting the actual assembly, Steve sketches an initial blueprint, placing the $$$n$$$ cuboids in a specific arrangement. Your task is to verify whether this blueprint satisfies the aforementioned conditions.

Input

The first line contains a single integer $$$T$$$ ($$$1\le T \le 10^4$$$), denoting the number of test cases.

For each test case, the first line contains three integers $$$W,H,L$$$ ($$$1\le W,H,L\le 10^9$$$), denoting the upper right corner of the larger cuboid structure.

The second line contains an integer $$$n$$$ ($$$1\le n \le 10^5$$$), denoting the number of cuboid materials.

Each of the next $$$n$$$ lines contains $$$6$$$ integers $$$x_l$$$, $$$y_l$$$, $$$z_l$$$, $$$x_r$$$, $$$y_r$$$, $$$z_r$$$ ($$$0\le x_l \lt x_r\le W$$$, $$$0\le y_l \lt y_r\le H$$$, $$$0\le z_l \lt z_r\le L$$$), denoting the coordinates of the cuboid, with its lower left at $$$(x_l,y_l,z_l)$$$ and its upper right at $$$(x_r,y_r,z_r)$$$.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$3\times 10^5$$$ over all test cases.

Output

For each test case, if the proposed arrangement in the blueprint satisfies the given conditions, output $$$\texttt{Yes}$$$ in a single line. Otherwise, output $$$\texttt{No}$$$ in a single line.

Example
Input
1
3 5 7
4
0 0 0 3 3 7
0 3 0 2 5 7
2 3 0 3 4 7
2 4 0 3 5 7
Output
Yes