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
/*	Arek Wróbel - skater
 *
 *	Zadanie: Parking
 *	Konkurs: PA2014, runda 3B
 */
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define REP(I, N) for(int I=0; I<(N); ++I)
#define FOR(I, M, N) for(int I=(M); I<=(N); ++I)
#define FORD(I, M, N) for(int I=(M); I>=(N); --I)
#define FOREACH(IT, CON) for(__typeof(CON.begin()) IT=CON.begin(); IT!=CON.end(); ++IT)
#define ST first
#define ND second
#define MP make_pair
#define PB push_back
const int INF=1000000000;
const LL INFLL=1000000000000000000LL;

int n, w;

struct ne {
	int x_st;
	int x_nd;
	int h;
} t[60000];

int perm[60000];

inline bool cmp_xst(const ne a, const ne b) {
	return a.x_st < b.x_st;
}
inline bool cmp2(const int a, const int b) {
	return t[a].x_nd < t[b].x_nd;
}

const int C = 1<<16;  // 65536
int T[2*C];

void clear() {
	REP(i, 2*C)
		T[i] = 0;
}

void put(int a, int h) {
	a+=C;
	T[a] = h;
	while (a>1) {
		T[a/2] = max(T[a/2], T[a]);
		a/=2;
	}
}

int get(int a) {
	a+=C;
	int wyn = T[a];
	while (a>1) {
		if (a & 1) {
			wyn = max(wyn, T[a-1]);
		}
		a/=2;
	}
	return wyn;
}

bool make() {
	clear();
	FORD(i, n-1, 0) {
//		printf(" %d: %d %d %d\n", i, perm[i], t[perm[i]].h, get(perm[i]));
		if (t[perm[i]].h + get(perm[i]) > w)
			return false;
		put(perm[i], t[perm[i]].h);
	}
	return true;
}

int main()
{
	int tests;
	scanf("%d", &tests);
	while(tests--) {
		//wej
		scanf("%d%d", &n, &w);
		REP(i, n) {
			int x1, y1, x2, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			t[i].x_st = min(x1, x2);
			t[i].h = abs(y1 - y2);
		}
		REP(i, n) {
			int x1, y1, x2, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			t[i].x_nd = min(x1, x2);
		}
		//prog
		sort(t, t+n, cmp_xst);
		REP(i, n)
			perm[i] = i;
		sort(perm, perm+n, cmp2);
//		REP(i, n) printf("%d: %d %d\n", i, perm[i], t[perm[i]].h);
		//wyj
		printf(make() ? "TAK\n" : "NIE\n");
	}
	return 0;
}