1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <deque>

#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i) 

using namespace std;

// MaxTree za "Algorytmika Praktyczna" Piotra Stanczyka.
const int INF = 1000001001;
struct MaxTree {
    int *el, s;
    MaxTree(int size) {
        el = new int[2 * (s = 1 << size)];
        REP(x, 2 * s) el[x] = 0;
    }
    ~MaxTree() {
        delete[]el;
    }
    void Set(int p, int v) {
        for (p += s, el[p] = v, p >>= 1; p > 0; p >>= 1)
            el[p] = max(el[p << 1], el[(p << 1) + 1]);
    }
    int Find(int p, int k) {
        int m = -INF;
        p += s;
        k += s;
        while (p < k) {
            if ((p & 1) == 1) m = max(m, el[p++]);
            if ((k & 1) == 0) m = max(m, el[k--]);
            p >>= 1;
            k >>= 1;
        }
        if (p == k) m = max(m, el[p]);
        return m;
    }
};

struct car {
    int h, pos, id;
    void get(int z) {
        id = z;
        int x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        h = max(y1, y2) - min(y1, y2);
        pos = min(x1, x2);
    }

    bool operator<(const car& x) const {
        if (pos != x.pos) return pos < x.pos;
        return id < x.id;
    }
};

const int MAX_N = 50100;
car d1[MAX_N], d2[MAX_N];
int mapping[MAX_N];

void fun() {
    int n, w;
    scanf("%d %d", &n, &w);
    REP(i, n) d1[i].get(i);
    REP(i, n) d2[i].get(i);

    sort(d1, d1+n);
    sort(d2, d2+n);

    REP(i, n) mapping[d1[i].id] = i;

    MaxTree tree(16);
    REP(i, n) tree.Set(i, d1[i].h);

    REP(i, n) {
        int pos_w_1 = mapping[d2[i].id];
        tree.Set(pos_w_1, 0);
        int m = tree.Find(0, pos_w_1);
        if (w - d2[i].h < m) {
            printf("NIE\n");
            return;
        }
    }

    printf("TAK\n");
    return;
}

int main() {
    int t;
    scanf("%d", &t);
    REP(i, t) fun();

    return 0;
}