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
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#define MAXN 50007
#define czapa 65536
#define INF
#define PB push_back
#define MP make_pair
#define ST first
#define ND second

#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(a,b,c) for(int a=b;a<=(c);a++)
#define FORD(a,b,c) for (int a=b;a>=(c);a--)
#define VAR(v,n) __typeof(n) v=(n)
#define ALL(c) c.begin(),c.end()
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++)

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;  

bool mozna;
int wys_park,testy,n,x_1,y_1,x_2,y_2;
int gdzie[MAXN],wys[MAXN];
int drzewo[2*czapa];
PII pocz[MAXN],kon[MAXN];

void insert(int poz, int v) {
	poz += czapa;
	drzewo[poz] = v;
	
	while (poz != 1) {
		poz /= 2;
		drzewo[poz] = max(drzewo[poz*2],drzewo[poz*2+1]);
	}
}

int query(int p) {
	int l = czapa;
	p += czapa;
	int res = max(drzewo[l],drzewo[p]);
	
	while (l/2 != p/2) {
		if (!(l&1)) res = max(res,drzewo[l+1]);
		if (p&1) res = max(res,drzewo[p-1]);
		l /= 2; p /= 2;
	}
	return res;
}

int main(){
	scanf("%d",&testy);
	while (testy--) {
		mozna = true;
		scanf("%d%d",&n,&wys_park);
		
		REP(i,n) {
			scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
			wys[i] = abs(y_1-y_2);
			pocz[i] = MP(min(x_1,x_2),i);
		}
		
		REP(i,n) {
			scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
			kon[i] = MP(min(x_1,x_2),i);
		}
		
		sort(pocz,pocz+n);
		sort(kon,kon+n);
		REP(i,n) gdzie[pocz[i].ND] = i;
		REP(i,n) insert(i,wys[pocz[i].ND]);
		REP(i,n) {
			insert(gdzie[kon[i].ND],0);
			if (query(gdzie[kon[i].ND]) + wys[kon[i].ND] > wys_park) mozna = false;
		}
		puts(mozna ? "TAK" : "NIE");
	}
	return 0;
}