<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
## 1. Abridged problem statement

Given a large right isosceles triangle with vertices:

```text
(0, 0), (0, n), (n, 0)
```

and `m` smaller triangles described by integer coordinates, determine whether the small triangles form a correct covering of the large triangle.

A covering is correct if:

1. every small triangle is right isosceles;
2. each small triangle’s catheti are horizontal/vertical;
3. every small triangle lies inside the large triangle;
4. no two small triangles overlap improperly;
5. the whole large triangle is covered.

For each test case, output `"YES"` or `"NO"`.

---

## 2. Key observations needed to solve the problem

### Observation 1: The large triangle is simple to test

The large triangle consists of all points satisfying:

```text
x >= 0
y >= 0
x + y <= n
```

Its doubled area is:

```text
n²
```

We use doubled areas to avoid floating-point computations.

---

### Observation 2: Valid small triangles have only four edge directions

If a small triangle is right isosceles and its catheti are parallel to the large triangle’s catheti, then:

- one cathetus is horizontal;
- one cathetus is vertical;
- the hypotenuse has slope `+1` or `-1`.

So every edge has one of four directions:

```text
horizontal
vertical
diagonal slope +1
diagonal slope -1
```

---

### Observation 3: Area equality is necessary but not sufficient

The sum of areas of all small triangles must equal the area of the large triangle.

However, this alone does not guarantee a valid covering, because triangles could overlap and leave holes elsewhere.

So we also need a local geometric consistency check.

---

### Observation 4: Use angle sums at vertices

At every relevant point, the total angle covered by small triangles must equal the angle of the large triangle at that point.

Expected angle:

| Point position | Expected angle |
|---|---:|
| `(0, 0)` | `90°` |
| `(n, 0)` or `(0, n)` | `45°` |
| On boundary but not a corner | `180°` |
| Strictly inside | `360°` |

Each valid small triangle contributes:

- `90°` at its right-angle vertex;
- `45°` at each acute vertex.

---

### Observation 5: Handle T-junctions

A vertex of one triangle may lie strictly inside an edge of another triangle:

```text
A ----- P ----- B
```

At point `P`, the edge `AB` contributes an additional straight angle:

```text
180°
```

Therefore, for every input vertex, we must count how many triangle edges strictly contain it.

---

### Observation 6: T-junctions can be found with 1D sweeps

Since edges have only four possible directions, for each direction we can project everything onto a line and solve interval stabbing.

For every direction:

| Direction | Line level | Position |
|---|---|---|
| Horizontal | `y` | `x` |
| Vertical | `x` | `y` |
| Slope `+1` | `y - x` | `x` |
| Slope `-1` | `x + y` | `x` |

For each line level:

- every edge becomes an interval `[lo, hi]`;
- every vertex becomes a query point.

We need to know how many intervals strictly contain each query point.

Use sweep events:

| Type | Meaning |
|---:|---|
| `0` | edge closes |
| `1` | vertex query |
| `2` | edge opens |

Sorting by:

```text
level, position, type
```

with order:

```text
close < query < open
```

ensures endpoints are not counted as being strictly inside an edge.

---

## 3. Full solution approach

For each test case:

### Step 1: Validate every small triangle

For each triangle, try each vertex as the right-angle vertex.

For a candidate right-angle vertex `A`, with other vertices `B` and `C`, define vectors:

```text
AB = B - A
AC = C - A
```

The triangle is valid if:

```text
AB · AC = 0
|AB|² = |AC|²
AB and AC are horizontal/vertical
```

Also verify each vertex lies inside the large triangle:

```text
x >= 0
y >= 0
x + y <= n
```

---

### Step 2: Check total area

Compute doubled area of each triangle using cross product:

```text
area2 = abs((B - A) × (C - A))
```

The sum must be exactly:

```text
n²
```

If not, answer is `"NO"`.

---

### Step 3: Compress all triangle vertices

Collect all input vertices and assign each unique point an integer id.

We will store the accumulated angle contribution for each unique vertex.

---

### Step 4: Add direct triangle angle contributions

For each valid triangle:

- add `90` to its right-angle vertex;
- add `45` to its other two vertices.

---

### Step 5: Add T-junction angle contributions

For each of the four edge directions:

1. Convert every edge of that direction into an interval.
2. Convert every unique vertex into a query.
3. Sort all events by `(level, position, type)`.
4. Sweep each line level independently.
5. At every query, add:

```text
180 * active_intervals
```

to that vertex’s angle sum.

Because of event order `close < query < open`, a vertex equal to an edge endpoint is not counted as lying inside that edge.

---

### Step 6: Compare with expected angles

For every unique input vertex:

- expected angle is determined by its position in the large triangle;
- compare with accumulated angle.

If all match, output `"YES"`, otherwise `"NO"`.

---

### Complexity

Let `V <= 3m` be the number of unique vertices.

For each of 4 directions we sort `O(m + V)` events.

Total complexity:

```text
O((m + V) log(m + V))
```

Memory complexity:

```text
O(m + V)
```

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Point {
    int x, y;
};

struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buffer[BUFSIZE];

    char getChar() {
        if (idx == size) {
            size = fread(buffer, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buffer[idx++];
    }

    int nextInt() {
        char c;
        do {
            c = getChar();
        } while (c <= ' ');

        int x = 0;
        while (c > ' ') {
            x = x * 10 + (c - '0');
            c = getChar();
        }
        return x;
    }
};

int64 dot(const Point& a, const Point& b, const Point& c) {
    int64 x1 = b.x - a.x;
    int64 y1 = b.y - a.y;
    int64 x2 = c.x - a.x;
    int64 y2 = c.y - a.y;
    return x1 * x2 + y1 * y2;
}

int64 cross(const Point& a, const Point& b, const Point& c) {
    int64 x1 = b.x - a.x;
    int64 y1 = b.y - a.y;
    int64 x2 = c.x - a.x;
    int64 y2 = c.y - a.y;
    return x1 * y2 - y1 * x2;
}

int64 dist2(const Point& a, const Point& b) {
    int64 dx = b.x - a.x;
    int64 dy = b.y - a.y;
    return dx * dx + dy * dy;
}

bool axisAligned(const Point& a, const Point& b) {
    return a.x == b.x || a.y == b.y;
}

bool insideLarge(const Point& p, int n) {
    return p.x >= 0 && p.y >= 0 && p.x + p.y <= n;
}

/*
    Returns the index of the right-angle vertex if the triangle is valid.

    A valid small triangle must:
    - be right;
    - be isosceles;
    - have horizontal/vertical catheti.

    Returns -1 if invalid.
*/
int rightAngleIndex(const array<Point, 3>& tri) {
    for (int i = 0; i < 3; i++) {
        int j = (i + 1) % 3;
        int k = (i + 2) % 3;

        const Point& a = tri[i];
        const Point& b = tri[j];
        const Point& c = tri[k];

        if (dot(a, b, c) != 0) continue;
        if (dist2(a, b) != dist2(a, c)) continue;
        if (!axisAligned(a, b)) continue;
        if (!axisAligned(a, c)) continue;

        return i;
    }

    return -1;
}

/*
    Direction classes:
    0 = horizontal
    1 = vertical
    2 = slope +1
    3 = slope -1
*/
int edgeDirection(int dx, int dy) {
    if (dy == 0) return 0;
    if (dx == 0) return 1;
    if (dx == dy) return 2;
    return 3;
}

struct DirInfo {
    int level;
    int pos;
};

/*
    Convert a point to a 1D position on a line of a given direction.

    d = 0: horizontal, level = y,     pos = x
    d = 1: vertical,   level = x,     pos = y
    d = 2: slope +1,   level = y - x, pos = x
    d = 3: slope -1,   level = x + y, pos = x
*/
DirInfo levelPos(int d, int x, int y) {
    if (d == 0) return {y, x};
    if (d == 1) return {x, y};
    if (d == 2) return {y - x, x};
    return {x + y, x};
}

string solveCase(int n, int m, vector<array<Point, 3>>& triangles) {
    vector<int> rightIdx(m);
    int64 totalArea2 = 0;

    /*
        Step 1 and 2:
        Validate triangle shape, validate inside-large condition,
        and compute total doubled area.
    */
    for (int i = 0; i < m; i++) {
        int r = rightAngleIndex(triangles[i]);
        if (r == -1) {
            return "NO";
        }

        rightIdx[i] = r;

        for (int j = 0; j < 3; j++) {
            if (!insideLarge(triangles[i][j], n)) {
                return "NO";
            }
        }

        totalArea2 += llabs(cross(triangles[i][0], triangles[i][1], triangles[i][2]));
    }

    if (totalArea2 != 1LL * n * n) {
        return "NO";
    }

    /*
        Compress all unique input vertices.
    */
    vector<pair<int, int>> allPts;
    allPts.reserve(3 * m);

    vector<array<int, 6>> triInt(m);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 3; j++) {
            int x = triangles[i][j].x;
            int y = triangles[i][j].y;

            triInt[i][2 * j] = x;
            triInt[i][2 * j + 1] = y;

            allPts.push_back({x, y});
        }
    }

    sort(allPts.begin(), allPts.end());
    allPts.erase(unique(allPts.begin(), allPts.end()), allPts.end());

    int V = (int)allPts.size();

    vector<array<int, 3>> triVid(m);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 3; j++) {
            pair<int, int> p = {
                triInt[i][2 * j],
                triInt[i][2 * j + 1]
            };

            triVid[i][j] =
                lower_bound(allPts.begin(), allPts.end(), p) - allPts.begin();
        }
    }

    /*
        angleAt[v] stores accumulated angle contribution at vertex v.
    */
    vector<int64> angleAt(V, 0);

    /*
        Add direct triangle angle contributions:
        - 90 degrees at right-angle vertex;
        - 45 degrees at each acute vertex.
    */
    for (int i = 0; i < m; i++) {
        int r = rightIdx[i];

        angleAt[triVid[i][r]] += 90;
        angleAt[triVid[i][(r + 1) % 3]] += 45;
        angleAt[triVid[i][(r + 2) % 3]] += 45;
    }

    /*
        We pack sweep events into uint64_t for fast sorting.

        Event ordering must be:
            close < query < open

        This guarantees that endpoints are not counted as being inside edges.
    */
    const int VID_BITS = 20;
    const int TYPE_SHIFT = VID_BITS;
    const int POS_SHIFT = TYPE_SHIFT + 2;
    const int LEVEL_SHIFT = POS_SHIFT + 17;
    const int LEVEL_OFFSET = 1 << 17;
    const uint64_t VID_MASK = (1ULL << VID_BITS) - 1;

    auto packEvent = [&](int level, int pos, int type, int vid) -> uint64_t {
        uint64_t shiftedLevel = (uint64_t)(level + LEVEL_OFFSET);
        uint64_t v = (uint64_t)(vid + 1);

        return (shiftedLevel << LEVEL_SHIFT)
             | ((uint64_t)pos << POS_SHIFT)
             | ((uint64_t)type << TYPE_SHIFT)
             | v;
    };

    vector<uint64_t> events;
    events.reserve(6 * m + V);

    /*
        Process four direction classes independently.
    */
    for (int d = 0; d < 4; d++) {
        events.clear();

        /*
            Add edge interval events.
        */
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                int nj = (j + 1) % 3;

                int ax = triInt[i][2 * j];
                int ay = triInt[i][2 * j + 1];

                int bx = triInt[i][2 * nj];
                int by = triInt[i][2 * nj + 1];

                if (edgeDirection(bx - ax, by - ay) != d) {
                    continue;
                }

                DirInfo a = levelPos(d, ax, ay);
                DirInfo b = levelPos(d, bx, by);

                int lo = min(a.pos, b.pos);
                int hi = max(a.pos, b.pos);

                // Open after queries at lo.
                events.push_back(packEvent(a.level, lo, 2, -1));

                // Close before queries at hi.
                events.push_back(packEvent(a.level, hi, 0, -1));
            }
        }

        /*
            Add one query event for each unique vertex.
        */
        for (int v = 0; v < V; v++) {
            int x = allPts[v].first;
            int y = allPts[v].second;

            DirInfo p = levelPos(d, x, y);
            events.push_back(packEvent(p.level, p.pos, 1, v));
        }

        sort(events.begin(), events.end());

        int currentLevel = INT_MIN;
        int active = 0;

        /*
            Sweep events by level and position.
        */
        for (uint64_t e : events) {
            int level = (int)(e >> LEVEL_SHIFT) - LEVEL_OFFSET;
            int type = (int)((e >> TYPE_SHIFT) & 3);
            int vidPlusOne = (int)(e & VID_MASK);

            if (level != currentLevel) {
                currentLevel = level;
                active = 0;
            }

            if (type == 0) {
                active--;
            } else if (type == 1) {
                int vid = vidPlusOne - 1;
                angleAt[vid] += 180LL * active;
            } else {
                active++;
            }
        }
    }

    /*
        Final check: every input vertex must have exactly the angle expected
        from its position in the large triangle.
    */
    for (int v = 0; v < V; v++) {
        int x = allPts[v].first;
        int y = allPts[v].second;

        int64 expected;

        if (x == 0 && y == 0) {
            expected = 90;
        } else if ((x == n && y == 0) || (x == 0 && y == n)) {
            expected = 45;
        } else if (x == 0 || y == 0 || x + y == n) {
            expected = 180;
        } else {
            expected = 360;
        }

        if (angleAt[v] != expected) {
            return "NO";
        }
    }

    return "YES";
}

int main() {
    FastScanner fs;

    int T = fs.nextInt();

    while (T--) {
        int n = fs.nextInt();
        int m = fs.nextInt();

        vector<array<Point, 3>> triangles(m);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 3; j++) {
                triangles[i][j].x = fs.nextInt();
                triangles[i][j].y = fs.nextInt();
            }
        }

        cout << solveCase(n, m, triangles) << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    ptr = 0

    T = data[ptr]
    ptr += 1

    answers = []

    # Constants for packed sweep events.
    VID_BITS = 20
    TYPE_SHIFT = VID_BITS
    POS_SHIFT = TYPE_SHIFT + 2
    LEVEL_SHIFT = POS_SHIFT + 17
    LEVEL_OFFSET = 1 << 17
    VID_MASK = (1 << VID_BITS) - 1

    def pack_event(level, pos, typ, vid):
        """
        Pack event into one integer.

        Events are sorted by:
            level, position, type, vertex_id

        type:
            0 = close
            1 = query
            2 = open

        This gives tie order:
            close < query < open
        """
        return (
            ((level + LEVEL_OFFSET) << LEVEL_SHIFT)
            | (pos << POS_SHIFT)
            | (typ << TYPE_SHIFT)
            | (vid + 1)
        )

    def dot(a, b, c):
        """
        Dot product of vectors AB and AC.
        """
        x1 = b[0] - a[0]
        y1 = b[1] - a[1]
        x2 = c[0] - a[0]
        y2 = c[1] - a[1]
        return x1 * x2 + y1 * y2

    def cross(a, b, c):
        """
        Cross product of vectors AB and AC.
        Its absolute value is the doubled area.
        """
        x1 = b[0] - a[0]
        y1 = b[1] - a[1]
        x2 = c[0] - a[0]
        y2 = c[1] - a[1]
        return x1 * y2 - y1 * x2

    def dist2(a, b):
        """
        Squared distance between two points.
        """
        dx = b[0] - a[0]
        dy = b[1] - a[1]
        return dx * dx + dy * dy

    def axis_aligned(a, b):
        """
        True if segment AB is horizontal or vertical.
        """
        return a[0] == b[0] or a[1] == b[1]

    def inside_large(p, n):
        """
        Check if point p lies inside or on the large triangle.
        """
        x, y = p
        return x >= 0 and y >= 0 and x + y <= n

    def right_angle_index(tri):
        """
        Return the right-angle vertex index if tri is valid.

        A valid triangle must:
        - be right;
        - be isosceles;
        - have horizontal/vertical catheti.

        Return -1 if invalid.
        """
        for i in range(3):
            j = (i + 1) % 3
            k = (i + 2) % 3

            a = tri[i]
            b = tri[j]
            c = tri[k]

            if dot(a, b, c) != 0:
                continue

            if dist2(a, b) != dist2(a, c):
                continue

            if not axis_aligned(a, b):
                continue

            if not axis_aligned(a, c):
                continue

            return i

        return -1

    def edge_direction(dx, dy):
        """
        Direction classes:
            0 = horizontal
            1 = vertical
            2 = slope +1
            3 = slope -1
        """
        if dy == 0:
            return 0
        if dx == 0:
            return 1
        if dx == dy:
            return 2
        return 3

    def level_pos(d, x, y):
        """
        Convert point to (level, position) for direction d.

        d = 0: horizontal, level = y,     pos = x
        d = 1: vertical,   level = x,     pos = y
        d = 2: slope +1,   level = y - x, pos = x
        d = 3: slope -1,   level = x + y, pos = x
        """
        if d == 0:
            return y, x
        if d == 1:
            return x, y
        if d == 2:
            return y - x, x
        return x + y, x

    for _ in range(T):
        n = data[ptr]
        m = data[ptr + 1]
        ptr += 2

        triangles = []

        for _i in range(m):
            x1, y1, x2, y2, x3, y3 = data[ptr:ptr + 6]
            ptr += 6

            triangles.append(((x1, y1), (x2, y2), (x3, y3)))

        right_idx = [-1] * m
        total_area2 = 0
        ok = True

        """
        Step 1 and 2:
        Validate all triangles and compute total doubled area.
        """
        for i, tri in enumerate(triangles):
            r = right_angle_index(tri)

            if r == -1:
                ok = False
                break

            right_idx[i] = r

            for p in tri:
                if not inside_large(p, n):
                    ok = False
                    break

            if not ok:
                break

            total_area2 += abs(cross(tri[0], tri[1], tri[2]))

        if not ok or total_area2 != n * n:
            answers.append("NO")
            continue

        """
        Compress all unique vertices.
        """
        all_points_list = []
        tri_int = []

        for tri in triangles:
            flat = []

            for x, y in tri:
                flat.append(x)
                flat.append(y)
                all_points_list.append((x, y))

            tri_int.append(flat)

        all_points = sorted(set(all_points_list))
        V = len(all_points)

        point_id = {p: i for i, p in enumerate(all_points)}

        tri_vid = []

        for flat in tri_int:
            ids = []

            for j in range(3):
                p = (flat[2 * j], flat[2 * j + 1])
                ids.append(point_id[p])

            tri_vid.append(ids)

        """
        angle_at[v] stores accumulated angle contribution at vertex v.
        """
        angle_at = [0] * V

        """
        Add direct angle contributions from triangle vertices.
        """
        for i in range(m):
            r = right_idx[i]
            ids = tri_vid[i]

            angle_at[ids[r]] += 90
            angle_at[ids[(r + 1) % 3]] += 45
            angle_at[ids[(r + 2) % 3]] += 45

        """
        Process T-junctions using four directional sweeps.
        """
        for d in range(4):
            events = []

            """
            Add interval events for all edges of direction d.
            """
            for flat in tri_int:
                for j in range(3):
                    nj = (j + 1) % 3

                    ax = flat[2 * j]
                    ay = flat[2 * j + 1]

                    bx = flat[2 * nj]
                    by = flat[2 * nj + 1]

                    if edge_direction(bx - ax, by - ay) != d:
                        continue

                    level_a, pos_a = level_pos(d, ax, ay)
                    level_b, pos_b = level_pos(d, bx, by)

                    lo = min(pos_a, pos_b)
                    hi = max(pos_a, pos_b)

                    # Edge opens after queries at lo.
                    events.append(pack_event(level_a, lo, 2, -1))

                    # Edge closes before queries at hi.
                    events.append(pack_event(level_a, hi, 0, -1))

            """
            Add query event for every unique vertex.
            """
            for vid, (x, y) in enumerate(all_points):
                level, pos = level_pos(d, x, y)
                events.append(pack_event(level, pos, 1, vid))

            events.sort()

            current_level = None
            active = 0

            """
            Sweep events.

            active is the number of currently open intervals on the same line.
            At a query, those intervals strictly contain the queried vertex.
            """
            for e in events:
                level = (e >> LEVEL_SHIFT) - LEVEL_OFFSET
                typ = (e >> TYPE_SHIFT) & 3
                vid_plus_one = e & VID_MASK

                if level != current_level:
                    current_level = level
                    active = 0

                if typ == 0:
                    active -= 1
                elif typ == 1:
                    vid = vid_plus_one - 1
                    angle_at[vid] += 180 * active
                else:
                    active += 1

        """
        Final angle verification.
        """
        for vid, (x, y) in enumerate(all_points):
            if x == 0 and y == 0:
                expected = 90
            elif (x == n and y == 0) or (x == 0 and y == n):
                expected = 45
            elif x == 0 or y == 0 or x + y == n:
                expected = 180
            else:
                expected = 360

            if angle_at[vid] != expected:
                ok = False
                break

        answers.append("YES" if ok else "NO")

    sys.stdout.write("\n".join(answers))


if __name__ == "__main__":
    solve()
```