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
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 50000;

struct Car {
    int id;
    int x;
    int w;
};

inline bool operator<(const Car &a, const Car &b) {
    return a.x < b.x;
}

Car initialOrder[MAXN];
Car desiredOrder[MAXN];
Car mergeTab[MAXN];
int id2DesiredIndex[MAXN];
bool checkRes;

bool cmp(int aId, int bId) {
    return (id2DesiredIndex[aId] <= id2DesiredIndex[bId]);
}

void merge(int l, int m, int r, int w) {
    int length = r-l+1;
    int i=0, j=l, k=m;
    while ((j <= m-1) && (k <= r)) {
        if (cmp(initialOrder[j].id, initialOrder[k].id)) {
	    mergeTab[i] = initialOrder[j];
	    i++; j++;
        }
	else {
	    mergeTab[i] = initialOrder[k];
            for (int z=j; z<m; z++)
                if (initialOrder[k].w + initialOrder[z].w > w)
                    checkRes = false;
	    i++; k++;
        }
    }

    while (j <= m-1) {
        mergeTab[i] = initialOrder[j];
        i++; j++;
    }

    while(k <= r) {
        mergeTab[i] = initialOrder[k];
        i++; k++;
    }

    i = 0;
    while(l <= r) {
        initialOrder[l] = mergeTab[i];
        i++; l++;
    }
}

void mergeSort(int l, int r, int w) {
    int m;
    if (r > l) {
        m = (r+l)/2;
        mergeSort(l, m, w);
        mergeSort(m+1, r, w);
        merge(l, m+1, r, w);
    }
}

bool check(int n, int w) {
    for (int i=0; i<n; i++) {
        id2DesiredIndex[desiredOrder[i].id] = i;
    }
    checkRes = true;
    mergeSort(0, n-1, w);
    return checkRes;
}

int main() {
    int t, n, w, x1, y1, x2, y2;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &w);
        for (int i=0; i<n; i++) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            initialOrder[i].id = i+1;
            initialOrder[i].x = min(x1, x2);
            initialOrder[i].w = abs(y1-y2);
        }
        for (int i=0; i<n; i++) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            desiredOrder[i].id = i+1;
            desiredOrder[i].x = min(x1, x2);
            desiredOrder[i].w = abs(y1-y2);
        }
        sort(initialOrder, initialOrder+n);
        sort(desiredOrder, desiredOrder+n);

        //printf("[DEBUG] Initial order:\n");
        for (int i=0; i<n; i++) {
            //printf("[DEBUG] %d: %d %d\n", initialOrder[i].id, initialOrder[i].x, initialOrder[i].w);
        }
        //printf("[DEBUG] Desired order:\n");
        for (int i=0; i<n; i++) {
            //printf("[DEBUG] %d: %d %d\n", desiredOrder[i].id, desiredOrder[i].x, desiredOrder[i].w);
        }

        bool res = check(n, w);
        if (res) printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}