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
98
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#define x first
#define y second
#define ABS(z) ((z)>0?(z):(-(z)))
using namespace std;
struct rect {
    pair<int,int> lc;
    pair<int,int> rc;
    int index;
    rect() {}
    rect(pair<int,int> lc, pair<int,int> rc) : lc(lc), rc(rc) {}
    int h() {
        return ABS(rc.y - lc.y);
    }
    int w() {
        return ABS(rc.x - lc.x);
    }
    rect in_zero() {
        return rect(make_pair(0,0), make_pair(rc.x - lc.x, rc.y - lc.y));
    }
};
inline bool operator<(const rect& a, const rect& b) {
    return a.rc.x < b.rc.x;
}
void add(int* tree, int x, int M, int v) {
    x += M;
    tree[x] = v;
    while(x!=1){
        x /= 2;
        tree[x] = max(tree[x*2], tree[x*2+1]);
    }
}
int query(int* tree,int M, int p, int q) {
    p += M;
    q += M;
    int out = max(tree[p],tree[q]);
    while(p<q) {
        if(!(p&1)) out = max(out,tree[p++]);
        if(q&1) out = max(out,tree[q--]);
        p/=2; q/=2;
    }
    return out;
}
int main() {
    int Z;
    scanf("%d",&Z);
    while(Z--) {
        int n,w;
        scanf("%d%d",&n,&w);
        vector<rect> before(n);
        vector<rect> after(n);
        int pos[n];
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d%d",&before[i].lc.x, &before[i].lc.y, &before[i].rc.x, &before[i].rc.y);
            before[i].index = i;
        }
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d%d",&after[i].lc.x, &after[i].lc.y, &after[i].rc.x, &after[i].rc.y);
            after[i].index = i;
        }
        sort(before.begin(), before.end());
        sort(after.begin(), after.end());
        int M = 1;
        while(M <= n) M*=2;
        int tree[4*M];
        for(int i = 0; i < 4*M; i++)
            tree[i] = 0;
        M /= 2;
        for(int i = 0; i < before.size(); i++) {
            add(tree,i,M,before[i].h());
            pos[before[i].index] = i;
        }
        bool fail = false;
        for(int i = 0; i < after.size(); i++) {
            if(pos[after[i].index] == i)
                continue;
            int p = i;
            int q = pos[after[i].index];
            if(p>q)
                swap(p,q);
            q--;
            int maxh = query(tree, M, p, q);
            //printf("    %d %d %d %d\n",after[i].index,p,q,maxh);
            if(w - maxh < after[i].h()) {
                fail = true;
                break;
            }
            int x = tree[M+i];
            add(tree, i, M, after[i].h());
            add(tree, pos[after[i].index], M, x);
        }
        printf(fail ? "NIE\n" : "TAK\n");
    }
    return 0;
}