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
#define debug if(0)
// Grzegorz Guspiel
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i=0;i<int(n);++i)
#define SIZE(c) ((int)((c).size()))
#define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second

template<typename T> void maxE(T& a, const T& b) { a = max(a, b); }
template<typename T> void minE(T& a, const T& b) { a = min(a, b); }

const int MAXN = 50100;

struct Rect {
    int x1, y1, y2;
    int id;
};
bool operator<(const Rect& a, const Rect& b) {
    if (a.x1 == b.x1) return a.y1 < b.y1;
    else return a.x1 < b.x1;
}

int n, w;
vector<Rect> initial;
vector<Rect> todo;
int where[MAXN];

void getOrder(vector<Rect>& rect) {
    rect.clear();
    REP (i, n) {
        Rect r;
        int x2;
        cin >> r.x1 >> r.y1 >> x2 >> r.y2;
        if (r.x1 > x2) swap(r.x1, x2);
        if (r.y1 > r.y2) swap(r.y1, r.y2);
        r.id = i;
        rect.pb(r);
    }
}

static struct {
    int s;
    int t[65536 * 2 + 10];
    void init(int s_) {
        s = 1;
        while (s <= s_) s *= 2;
        REP (i, 2 * s) t[i] = 0;
    }
    void tupd(int a) {
        if (!a) return;
        t[a] = max(t[2 * a], t[ 2 * a + 1]);
        tupd( a/ 2);
    }
    int tget(int a, int b) {
        if (a > b) return 0;
        if (a == b) return t[a];
        int r = 0;
        if (a % 2) r = max(r, t[a++]);
        if (b % 2 == 0) r = max(r, t[b--]);
        return max(r, tget(a/2, b/2));
    }
    void set(int a, int b) {
        t[s + a] = b;
        tupd((s + a) / 2);
    }
    int get(int a, int b) { return tget(s + a, s + b); }
} tree;

bool weCan() {
    tree.init(n + 1);
    sort(ALL(initial));
    sort(ALL(todo));
    REP (i, n) where[initial[i].id] = i;
    REP (i, n) tree.set(i, initial[i].y2 - initial[i].y1);
    FOREACH (i, todo) {
        int j = where[i->id];
        int mine = initial[j].y2 - initial[j].y1;
        debug cout << "try to move " << j << " hei " << mine << endl;
        int his = tree.get(0, j - 1);
        if (mine + his > w) {
            return 0;
        }
        tree.set(j, 0);
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
	int z; cin >> z;
	while(z--) {
        cin >> n >> w;

        getOrder(initial);
        getOrder(todo);

        if (weCan()) cout << "TAK" << endl;
        else cout << "NIE" << endl;
	}
	return 0;
}