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
#include <cstdio>
#include <algorithm>
#include <vector>

#define ST first
#define ND second

using namespace std;

const int MX = 1<<16;

int n, w, tr[MX*2];

void insert(int u, int v) {
    u += MX;
    tr[u] = v;
    u /= 2;
    while (u) {
        tr[u] = max(tr[u*2], tr[u*2+1]);
        u /= 2;
    }
}

int query(int a, int b) {
    a += MX; b += MX;
    if (a > b) return 0;
    int r = max(tr[a], tr[b]);
    while (a/2 != b/2) {
        if (a%2 == 0) r = max(r, tr[a+1]);
        if (b%2 == 1) r = max(r, tr[b-1]);
        a /= 2; b /= 2;
    }
    return r;
}

struct car {
    int x1, y1, x2, y2;
    void read() {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
    }
    int h() {
        return y2 - y1;
    }
    bool operator<(car B) const {
        return x1 < B.x1;
    }
};

pair<car, car> C[MX];
int o[MX];

int cmp_ND(int a, int b) {
	return C[a].ND < C[b].ND;
}

bool solve() {
    fill(tr, tr+MX*2, 0);
    scanf("%d%d", &n, &w);
    for (int i = 1; i <= n; i++) C[i].ST.read();
    for (int i = 1; i <= n; i++) C[i].ND.read();
    sort(C+1, C+n+1);
    //for (int i = 1; i <= n; i++) printf("%d %d %d %d\n", C[i].ST.x1, C[i].ST.y1, C[i].ST.x2, C[i].ST.y2);
    for (int i = 1; i <= n; i++) insert(i, C[i].ST.h());
    for (int i = 1; i <= n; i++) o[i] = i;
    sort(o+1, o+n+1, cmp_ND);
    //printf("start\n");
    for (int i = 1; i <= n; i++) {
        int u = o[i];
        //printf("%d %d\n", u, C[u].ST.h());
        if (query(0, u-1) + C[u].ST.h() > w) return false;
        insert(u, 0);
    }
    return true;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        printf(solve() ? "TAK\n" : "NIE\n");
    }
    return 0;
}