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

typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
typedef vector<int> vi;

inline int read() { int n; scanf("%d", &n); return n; }

class MaxRT {
    vi t;
    int nn;
    int tmpmax(int i, int j, int a, int b, int id);
public:
    MaxRT(int n);
    void set(int i, int v);
    int max(int i, int j);
    int get(int i);
};

MaxRT::MaxRT(int n) {
    nn = n-1;
    nn |= (nn >> 1);
    nn |= (nn >> 2);
    nn |= (nn >> 4);
    nn |= (nn >> 8);
    nn |= (nn >> 16);
    nn++;
    t = vi(2*nn, 0);
}

void MaxRT::set(int i, int v) {
    i += nn;
    t[i] = v;
    for (i/=2; i>0; i/=2)
        t[i] = std::max(t[2*i], t[2*i+1]);
}

int MaxRT::max(int i, int j) {
    return tmpmax(i, j, 0, nn-1, 1);
}

int MaxRT::tmpmax(int i, int j, int a, int b, int id) {
    if (j < a || b < i)
        return 0;
    if (i < a)
        i = a;
    if (b < j)
        j = b;
    if (i == a && j == b)
        return t[id];
    return std::max(tmpmax(i, j, a, (a+b)/2, 2*id), tmpmax(i, j, (a+b)/2+1, b, 2*id+1));
}

int MaxRT::get(int i) {
    return t[i+nn];
}

bool oneCase(int n) {
    int w = read();
    vector<pii> a(n);
    for (int i=0; i<n; ++i) {
        int x1 = read();
        read();
        int x2 = read();
        read();
        int x3 = std::min(x1, x2);
        a[i] = mp(x3, i);
    }
    sort(a.begin(), a.end());
    vi m(n);
    for (int i=0; i<n; ++i)
        m[a[i].second] = i;
    MaxRT rt(n);
    for (int i=0; i<n; ++i) {
        int x1 = read();
        int y1 = read();
        int x2 = read();
        int y2 = read();
        int x3 = std::min(x1, x2);
        a[i] = mp(x3, m[i]);
        rt.set(m[i], std::abs(y2 - y1));
    }
    sort(a.begin(), a.end());
    for (int i=0; i<n; ++i) {
        int id = a[i].second;
        if (id > 0 && rt.get(id) + rt.max(0, id - 1) > w)
            return false;
        rt.set(id, 0);
    }
    return true;
}

int main() {
    int t = read();
    while (t--)
        printf("%s\n", oneCase(read()) ? "TAK" : "NIE");
    return 0;
}