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
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <cstring>
#include <list>
#include <iostream>
using namespace std;
#define FOR(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i <= n; i++)
#define FORI(it,n)for(typeof(n.begin()) it = n.begin(); it != n.end(); it++)
#define frs first
#define sec second
#define psh push_back
#define mkp make_pair
typedef long long LL;
typedef long double LD;

const int INF = 2147483647;
const int MAX = 50100;

struct Car {
	int x1,x2;
	int w;
};

int n, w;
Car A[2][MAX];
int I[2][MAX];
int P[MAX], B[MAX];

struct {
	int t[MAX * 4];
	int x, y;
	int find(int a, int b, int k) {
		if(a == b && a == x) return k;
		int sr = (a + b) / 2; //(1 + 2) / 2 = 1
		if(sr >= x) return find(a, sr, k << 1);
		else return find(sr + 1, b, (k << 1) + 1);
	}
	void fix(int a) {
		if(a == 1) return;
		int k = a >> 1;
		t[k] = max(t[k << 1], t[(k << 1) + 1]);
		fix(k);
	}
	void put(int a, int v) {
		x = a;
		a = find(0, n - 1, 1);
		t[a] = v;
		fix(a);
	}
	void remove(int a) {
		put(a, 0);
	}
	int get(int a, int b, int k) {
		if((a >= x) && (b <= y)) return t[k];
		int sr = (a + b) / 2;
		int r = 0;
		if(x <= sr) r = get(a, sr, (k << 1));
		if(y > sr) r = max(get(sr + 1, b, (k << 1) + 1), r);
		return r;
	}
	int get(int a) {
		if(a < 0) return 0;
		x = 0;
		y = a;
		return get(0, n - 1, 1);
	}
} T;

bool solve() {
	int y1,y2,a;
	scanf("%d%d", &n, &w);
	FOR(t,2) FOR(i,n) {
		scanf("%d%d%d%d", &A[t][i].x1, &y1, &A[t][i].x2, &y2);
		if(A[t][i].x1 > A[t][i].x2) swap(A[t][i].x1, A[t][i].x2);
		A[t][i].w = abs(y1 - y2);
		I[t][i] = i;
	}

	sort(I[0], I[0] + n, [](int a, int b) { return A[0][a].x1 < A[0][b].x1; });
	sort(I[1], I[1] + n, [](int a, int b) { return A[1][a].x1 < A[1][b].x1; });
	FOR(i,n) B[I[0][i]] = i;

	FOR(i,n) T.put(i, A[0][I[0][i]].w);
	FOR(i,n) {
		a = I[1][i];
		//fprintf(stderr, "%d(%d): %d\n", a, B[a], T.get(B[a] - 1));
		if(A[0][a].w + T.get(B[a] - 1) > w) return false;
		T.remove(B[a]);
	}

	return true;
}

int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		if(solve()) printf("TAK\n");
		else printf("NIE\n");
		memset(&T, 0, sizeof(T));
	}
}