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
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
const int N=50000;
struct R {
    int x1,y1,x2,y2,i;
    R *l,*r;
    set<int> ls,rs;
    int h()const{return y2-y1;}
    void fix(){if(x1>x2)swap(x1,x2);if(y1>y2)swap(y1,y2);}
}r1[N],r2[N];
int n,w;
R *sl[N],*sr[N];
bool opx1(R *ra,R *rb){return ra->x1!=rb->x1?ra->x1<rb->x1:ra->i<rb->i;}
bool opx2(R *ra,R *rb){return ra->x2!=rb->x2?ra->x2<rb->x2:ra->i<rb->i;}
struct oph{bool operator()(R *ra,R *rb)const{return ra->h()>rb->h();}};
void bounds(R *r){
    for (int i=0;i<n;++i){sl[i]=sr[i]=r+i;}
    sort(sl,sl+n,&opx1);sort(sr,sr+n,&opx2);
    multiset<R*,oph> sw;
    for (int i=0;i<n;++i){
        while(!sw.empty() && (*sw.begin())->h()+sl[i]->h()>w)
        {(*sw.begin())->r=sl[i];sl[i]->ls.insert((*sw.begin())->i);sw.erase(sw.begin());}
        sw.insert(sl[i]);
    }
    sw.clear();
    for (int i=n-1;i>=0;--i){
        while(!sw.empty() && (*sw.begin())->h()+sr[i]->h()>w)
        {(*sw.begin())->l=sr[i];sr[i]->rs.insert((*sw.begin())->i);sw.erase(sw.begin());}
        sw.insert(sr[i]);
    }
}
bool rel(int i){
    return (((!r1[i].l&&!r2[i].l)||(r1[i].l&&r2[i].l&&r1[i].l->i==r2[i].l->i)) &&
            ((!r1[i].r&&!r2[i].r)||(r1[i].r&&r2[i].r&&r1[i].r->i==r2[i].r->i))) ||
           (r1[i].ls==r2[i].ls&&r1[i].rs==r2[i].rs);
}
bool test(){
    scanf("%d%d",&n,&w);
    for(int i=0;i<n;++i) {scanf("%d%d%d%d",&r1[i].x1,&r1[i].y1,&r1[i].x2,&r1[i].y2);r1[i].fix();}
    for(int i=0;i<n;++i) {scanf("%d%d%d%d",&r2[i].x1,&r2[i].y1,&r2[i].x2,&r2[i].y2);r2[i].fix();}
    for(int i=0;i<n;++i) {r1[i].i=r2[i].i=i;r1[i].l=r1[i].r=r2[i].l=r2[i].r=0;r1[i].ls.clear();r1[i].rs.clear();r2[i].ls.clear();r2[i].rs.clear();}
    bounds(r1); bounds(r2);
    for(int i=0;i<n;++i) if(!rel(i)) return false;
    return true;
}
int main(){
    int t;
    scanf("%d",&t);
    for (int i=0;i<t;++i)printf(test()?"TAK\n":"NIE\n");
    return 0;
}