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
#include <cstdio>
#include <algorithm>
#include <vector>
#include<iostream>
#define fru(j,n) for(int j=0;j<n;++j)
#define tr(it,x) for(typeof(x.begin())it=x.begin();it!=x.end();++it)
#define x first
#define y second

using namespace std;
typedef pair<int,int> pii;
typedef long long LL;
const int MAXN = 50003,T=64*1024;
int nr[MAXN],perm[MAXN],hei[MAXN];
vector<pair<pii,int> > V;
vector<int>drz;
void insert(int a,int co)
{
    a+=T;
    drz[a]=co;
    a/=2;
    while(a>0)
    {
        drz[a]=max(drz[2*a],drz[2*a+1]);
        a/=2;
    }
}
int get(int a)
{
    int b=2*T,wyn=0;
    a+=T;
    while(a<=b)
    {
        if(a%2==1){wyn=max(wyn,drz[a]);a++;}
        if(a%2==0){wyn=max(wyn,drz[b]);b--;}
        a/=2;b/=2;
    }
    return wyn;
}

void solve()
{
    int n,w,x1,x2,y1,y2;
    scanf("%d%d",&n,&w);
    V.clear();
    drz.clear();drz.resize(2*T,0);
    fru(i,n)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        V.push_back(make_pair(pii(min(x1,x2),min(y1,y2)),i));
    }
    sort(V.begin(),V.end());
    fru(i,n)nr[V[i].y]=i;
    V.clear();
    fru(i,n)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        V.push_back(make_pair(pii(min(x1,x2),min(y1,y2)),nr[i]));
        hei[nr[i]]=abs(y1-y2);
    }
    sort(V.begin(),V.end());
    fru(i,n)perm[V[i].y]=i;
   // printf("perm\n");
    //fru(i,n)printf("%d ",nr[i]);puts("");
    //fru(i,n)printf("%d ",perm[i]);puts("");
    //fru(i,n)printf("%d ",hei[i]);puts("");
    bool ok=true;
    fru(i,n)
    {
        //printf("mam %d\n",i);
        insert(perm[i],hei[perm[i]]);
        if(get(perm[i]+1)+hei[perm[i]]>w){ok=false;break;}
    }
    if(ok)puts("TAK");
    else puts("NIE");
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}