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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct sam{
    int x, h, n;
    bool operator<(const sam& d) const {
        return (x<d.x);
    }
    bool operator==(const sam& d) const {
        return (x==d.x && n==d.n && h==d.h);
    }
}s;

int A[10000000];
int D[10000000];
int cant_touch_this(int x, int p, int q, int k, int l) {
    int a=0, b=0;
    if(k==p && l==q)
        return D[x];
    else
    {
        int m=(k+l)/2;
        if(p <= m)
            a=cant_touch_this( 2*x, p, min (m, q), k, m);
        if(q > m)
            b=cant_touch_this( 2*x+1, max(p, m + 1), q, m+1, l);
    }
    return max(a, b);
}

void build(int x, int s) {
    if(x>=s) return;
    else
    {
        build(2*x, s);
        build(2*x + 1, s);
        D[x]=max(D[2*x], D[2*x + 1]);
    }
    return;
}

void zerowanko(int x) {
    D[x]=0;
    do {
    x/=2;
    D[x]=max(D[2*x], D[2*x+1]); }
    while(x>1);
}

int main () {
    ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    vector<sam> V, W;
    for(int tt=0; tt<t; tt++)
    {
        int n, w;
        int x1, x2, y1, y2;
        cin>>n>>w;
        for(int i=1; i<=n; i++)
        {
            cin>>x1>>y1>>x2>>y2;
            s.n=i;
            s.x=min(x1, x2);
            s.h=max(y1, y2) - min(y1, y2);
            V.push_back(s);
        }
        for(int i=1; i<=n; i++)
        {
            cin>>x1>>y1>>x2>>y2;
            s.n=i;
            s.x=min(x1, x2);
            s.h=max(y1, y2) - min(y1, y2);
            W.push_back(s);
        }
        sort(V.begin(), V.end());
        sort(W.begin(), W.end());

        int d=1;
        while(d<n) d*=2;
        s.h=s.x=s.n=0;
        for(int i=1; i<=d-n; i++)
            V.push_back(s);

        for(int i=0; i<n; i++)
        {
            A[ V[i].n ]=i+1;
            D[d+i]=V[i].h;
        }
        build(1, d);

        int h, k;
        bool c=true;
        for(int i=0; i<n; i++)
        {
            k=A[ W[i].n ];
            zerowanko(k+d-1);

            h=cant_touch_this(1, 1, k, 1, d );
            if(w-h < W[i].h)
            {
                c=false;
                break;
            }
        }

        (c) ? cout<<"TAK"<<endl : cout<<"NIE"<<endl;
        V.clear();
        W.clear();
    }
    return 0;
}