474. All for Love

Time limit per test: 1.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Masha has already tried all traditional ways to attract attention of Misha. The last chance to win the desired man is to use magic. And the most suitable moment to use magic is Halloween evening. To summon dark forces she bought large magic plate and a set of small plates. Every plate has a form of the right isosceles triangle. To achieve a magic effect, one need to completely cover the large plate with small ones. Moreover, every small plate should be placed in such a way that each of it's cathetuses is parallel to some cathetus of the large plate. To make the process of covering easier, an instruction is included into magic collection. Instruction says: let's introduce coordinate system in such a way that the large plate will become a triangle with vertices in (0, 0), (0, n) and (n, 0). Then the instruction gives the exact position of every small plate in this coordinate system. Masha carefully followed this instruction and constructed the coverage. But she is still in doubt: what if the instruction is wrong and all efforts are useless? This question gives her no sleep, and she asks you to verify the instruction. More formally, let's call a coverage of the large triangle by small triangles correct if all the following conditions hold:
  • all triangles are right and isosceles,
  • no two triangles cross,
  • every triangle is inside the large one,
  • every part of the large triangle is covered by some small triangle.





An example of the correct coverage.

Input
Input consits of several test cases. The first line contains one positive integer t ≤ 10 — the number of test cases. Every case starts with a line with two integers n and m — the length of the large triangle's cathetus and the number of small triangles in the coverage correspondingly (1 ≤ n ≤ 25000, 1 ≤ m ≤ 100000). The rest of the test case consists of m lines containing 6 non-negative integers each: x1, y1, x2, y2, x3, y3, which denote the coordinates of vertices of the small triangles. These numbers don't exceed 25000. Every triangle is guaranteed to be nondegenerate. Total number of triangles in all test cases doesn't exceed 200000.

Output
For every test case output one line with a word "
YES
", if the given coverage is correct, and "
NO
" otherwise.

Example(s)
sample input
 
sample output
 
3
1 1
0 0 0 1 1 0
2 3
0 0 1 1 0 1
0 1 1 1 0 2
1 1 2 0 1 0
3 6
0 0 0 1 1 1
0 0 1 0 1 1
1 0 1 1 2 1
1 0 2 0 2 1
2 0 2 1 3 0
0 1 2 1 0 3

YES
NO
YES