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
#include<stdio.h>
#include<algorithm>
using namespace std;

struct car {
    int id;
    int x;
    int y;
};

const bool cmp(const car &a, const car &b) {
    return a.x < b.x;
}

struct node {
    int v;
    int a;
    int b;
    int p,l,r;
};


int z;
int n,w;
int a1,a2,b1,b2;

car T1[50010];
car T2[50010];
int R[50010];

node T[150010];

int P[30];

int main() {
    scanf("%d", &z);
    
    P[0] = 1;
    for(int i=1;i<20;i++)
        P[i] = P[i-1]*2;

    while(z--) {
        scanf("%d %d", &n, &w);
        for(int i=0;i<n;i++) {
            scanf("%d %d %d %d", &a1, &b1, &a2, &b2);
            T1[i].id = i;
            T1[i].x = min(a1, a2);
            T1[i].y = max(b1, b2) - min(b1, b2);
        }
        sort(T1,T1+n,cmp);

        for(int i=0;i<n;i++)
            R[T1[i].id] = i;

        for(int i=0;i<n;i++) {
            scanf("%d %d %d %d", &a1, &b1, &a2, &b2);
            T2[i].id = i;
            T2[i].x = min(a1, a2);
            T2[i].y = max(b1, b2) - min(b1, b2);
        }
        sort(T2, T2+n,cmp);

        
        T[0].a = 0; T[0].b = 0;
        T[0].v = -1;
        T[0].p = -1; T[0].l = -1; T[0].r = -1;

        int k = 0;
        int q = n+1;
        for(int i=1;i<=n;i++) {
            T[i].a = i; T[i].b = i;
            T[i].v = T1[i-1].y;
            T[i].l = -1; T[i].r = -1; T[i].p = -1;
        }

        while(k+1 < q) {
            if(T[k].p == T[k+1].p) {
                T[q].l = k; T[q].r = k+1;
                T[q].v = max(T[k].v, T[k+1].v);
                T[q].p = T[k].p-1;
                T[q].a = T[k].a; T[q].b = T[k+1].b;
                T[k].p = q; T[k+1].p = q;
                q++; k+=2;
            }
            else {
                T[q].l = k; T[q].r = k;
                T[q].v = T[k].v;
                T[q].p = T[k].p-1;
                T[q].a = T[k].a; T[q].b = T[k].b;
                T[k].p = q;
                q++; k++;
            }
        }


/*        for(int i=0;i<q;i++) {
            printf("[%d, %d] -> %d\n", T[i].a, T[i].b, T[i].v);
        }*/

        bool ok = true;
        for(int i=0;i<n;i++) {
            int id = R[T2[i].id];
    
            int c = k;
            int mm = -1;
            while(id != T[c].b) {
                if(id <= T[T[c].l].b) {
                    c = T[c].l;
                }
                else {
                    mm = max(mm, T[T[c].l].v);
                    c = T[c].r;
                }
            }
            mm = max(mm, T[c].v);
            if(mm + T2[i].y > w) {
//                printf("%d %d %d\n", T2[i].id, mm, T2[i].y);
                ok = false;
                break;
            }


            T[id+1].v = -1;
            c = id+1;
            while(T[c].p > 0) {
                int newv = max(T[T[T[c].p].l].v, T[T[T[c].p].r].v);
                if(newv == T[T[c].p].v) {
                    break;
                }
                T[T[c].p].v = newv;
                c = T[c].p;
            }
        }
        
        if(ok) printf("TAK\n");
        else printf("NIE\n");
    }


    return 0;
}