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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORD(i,a,b) for (int i = (b) - 1; i >= (a); --i)
#define REPD(i,n) FORD(i,0,n)

struct C {
	int i, x, y;
};

bool operator<(const C& c1, const C& c2) {
	return c1.x < c2.x;
}

int n, w, tt;
C a[50000], b[50000];
int at[50000], bt[50000], al[50000], bl[50000], ar[50000], br[50000];

void go(C* c, int* t, int* l, int* r) {
	REP(i,n) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		c[i].i = i;
		c[i].x = min(x1, x2);
		c[i].y = abs(y1 - y2);
	}
	sort(c, c + n);
	tt = 0;
	REP(i,n) if (c[i].y << 1 > w) t[tt++] = c[i].i;
	REP(i,n) l[i] = r[i] = -1;
	map<int, int> big;
	REP(i,n) if (c[i].y << 1 > w) {
		big[c[i].y] = c[i].i;
	} else {
		map<int, int>::iterator it = big.lower_bound(w - c[i].y + 1);
		if (it != big.end()) l[c[i].i] = it->second;
	}
	big.clear();
	REPD(i,n) if (c[i].y << 1 > w) {
		big[c[i].y] = c[i].i;
	} else {
		map<int, int>::iterator it = big.lower_bound(w - c[i].y + 1);
		if (it != big.end()) r[c[i].i] = it->second;
	}
}

int main() {
	int z;
	scanf("%d", &z);
	REP(zz,z) {
		scanf("%d%d", &n, &w);
		go(a, at, al, ar);
		go(b, bt, bl, br);
		bool ok = 1;
		REP(i,tt) if (at[i] != bt[i]) {
			ok = 0;
			break;
		}
		if (ok) REP(i,n) if (al[i] != bl[i] || ar[i] != br[i]) {
			ok = 0;
			break;
		}
		printf(ok ? "TAK\n" : "NIE\n");
	}
}