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
99
// Karol Kosinski
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <set>
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
//#define DEBUG(args...) printf(args)
#define DEBUG(args...)
#define NX 50003
using namespace std;

struct rect {
        int x, y, h, no;
} R[NX];

bool operator < (const rect &a, const rect &b) {
        if(a.x - b.x != 0) return a.x - b.x < 0;
        return a.y - b.y > 0;
}

struct edge {
        int a, b;
};

bool operator < (const edge &x, const edge &y) {
        if(x.a - y.a != 0) return x.a - y.a < 0;
        return x.b - y.b < 0;
}

bool operator == (const edge &x, const edge &y) {
        return x.a - y.a == 0 && x.b - y.b == 0;
}

struct cmp {
        bool operator () (int a, int b) {
                return R[a].h - R[b].h < 0;
        }
};

void add_edge(int x, int y, set<edge> &S) {
        DEBUG("\t( %d, %d )\n", R[x].no, R[y].no);
        edge e = (edge){ R[x].no, R[y].no };
        S.insert(e);
}

void build(int n, int w, set<edge> &S) {
        FOR(i,0,n) {
                int T[4];
                FOR(j,0,4) scanf("%d", T + j);
                R[i] = (rect){ min(T[0], T[2]),
                               max(T[1], T[3]),
                               abs(T[1] - T[3]),
                               i + 1 };
        }
        sort(R, R + n);
        set<int, cmp> Long;
        priority_queue<int, vector<int>, cmp> Short;
        FOR(i,0,n) {
                int ch = R[i].h;
                if( ch > w / 2 ) {
                        DEBUG("[%d] %d / %d\n", R[i].no, R[i].h, w);
                        if(!Long.empty()) {
                                set<int, cmp>::iterator it = Long.begin();
                                add_edge(*it, i, S);
                                while(!Long.empty() && R[*it].h <= ch) {
                                        Long.erase(it);
                                        it = Long.begin();
                                }
                        }
                        Long.insert(i);
                        while(!Short.empty() && R[Short.top()].h > w - ch) {
                                add_edge(Short.top(), i, S);
                                Short.pop();
                        }
                } else {
                        DEBUG("(%d) %d / %d\n", R[i].no, R[i].h, w);
                        Short.push(i);
                        R[NX - 1].h = w - ch;
                        set<int, cmp>::iterator it;
                        it = Long.upper_bound(NX - 1);
                        if(it != Long.end()) add_edge(*it, i, S);
                }
        }
}

bool testcase() {
        int n, w;
        scanf("%d%d", &n, &w);
        set<edge> A, B;
        build(n, w, A), build(n, w, B);
        return A == B;
}

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