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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 50050;

int DA[N*3];
int DB[N*3];

int pos1[N];
int pos2[N];

vector<pair<int,int> > P1;
vector<pair<int,int> > PP1, PP2;

bool spr(int a, int b, int c, int d)
{
    return (a < b && c < d) || (a > b && c > d);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        P1.clear();
        PP1.clear();
        PP2.clear();


        int n,W;
        int x1,y1,x2,y2;
        scanf("%d%d",&n,&W);

        P1.resize(n);
        PP1.resize(n);
        PP2.resize(n);
        int RD=1;
        while(RD<n) RD<<=1;

        for(int i=0;i<2*RD+2;++i) DA[i]=DB[i]=0;

        for(int i=0;i<n;++i)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            P1[i]=make_pair(max(y2,y1)-min(y2,y1),i);
            PP1[i]=make_pair(min(x1,x2),i);
        }
        for(int i=0;i<n;++i)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            PP2[i]=make_pair(min(x1,x2),i);
        }

        sort(P1.begin(), P1.end());
        sort(PP1.begin(), PP1.end());
        sort(PP2.begin(), PP2.end());

        for(int i=0;i<n;++i)
        {
            pos1[PP1[i].second]=i;
            pos2[PP2[i].second]=i;
        }

        int ow=-1;
        for(int i=n-1;i>=0;--i)
        {
            if (ow == -1)
            {
                if (i<n-1&&P1[i].first+P1[i+1].first<=W)
                    ow=i+1;
            }
            if (ow!=-1)
            {
                while(ow<n&&P1[ow].first+P1[i].first<=W)
                {
                    int i1=RD+pos1[P1[ow].second];
                    while(i1)
                    {
                        --DA[i1];
                        i1>>=1;
                    }
                    int i2=RD+pos2[P1[ow].second];
                    while(i2)
                    {
                        --DB[i2];
                        i2>>=1;
                    }
                    ++ow;

                }
            }

            int s1=0,s2=0;
            int iw1=RD+pos1[P1[i].second];
            while(iw1)
            {
                if (iw1%2==0)
                {
                    s1+=DA[iw1];
                    --iw1;
                }
                iw1 >>=1;
            }
            int iw2=RD+pos2[P1[i].second];
            while(iw2)
            {
                if (iw2%2==0)
                {
                    s2+=DB[iw2];
                    --iw2;
                }
                iw2 >>=1;
            }
            if (s1 != s2)
            {
                    printf("NIE\n");
                    //cout << s1 << " " << s2;
                    goto abc;
            }
            else
            {
                if (ow==-1)
                {
                    iw1=RD+pos1[P1[i].second];
                    while(iw1)
                    {
                        ++DA[iw1];
                        iw1>>=1;
                    }
                    iw2=RD+pos2[P1[i].second];
                    while(iw2)
                    {
                        ++DB[iw2];
                        iw2>>=1;
                    }
                }

            }

        }
        printf("TAK\n");
        abc:;
    }

    return 0;
}