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
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define vii vector<pair<int, int> >
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define mini(a,b) a=min(a,(b))
#define maxi(a,b) a=max(a,(b))
#define RE(i,n) for(int i=0,_n=(n);i<_n;++i)
#define RI(i,n) for(int i=1,_n=(n);i<=_n;++i)
#define h first
#define id second
const int inf=1e9+5, nax=50123, pot = 64 * 1024;

int n, H, odw[nax], tr[2 * pot + 5];
vector<pair<int, pii > > in;
vii start, wend;

vii parsuj() {
	RE(i, n) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		in.pb(mp(
			min(x1, x2),
			mp(abs(y2 - y1), i)
		));
	}
	sort(in.begin(), in.end());
	vii w;
	RE(i, in.size()) w.pb(in[i].nd);
	in.clear();
	return w;
}

bool test()
{
	RE(i, n) tr[pot + i] = wend[i].h;
	for(int i = pot - 1; i > 0; --i)
		tr[i] = max(tr[2 * i], tr[2 * i + 1]);
	RE(i, n) {
		int cel = odw[start[i].id];
		int m = 0;
		for(int x = pot + cel; x > 0; x /= 2)
			if(x % 2)
				maxi(m, tr[x - 1]);
		if(m + start[i].h > H) return false;
		tr[pot + cel] = 0;
		for(int x = (pot + cel) / 2; x > 0; x /= 2)
			tr[x] = max(tr[2 * x], tr[2 * x + 1]);
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(0);
	
	int z;
	cin >> z;
	while(z--) {
		cin >> n >> H;
		start = parsuj();
		wend = parsuj();
		RE(i, n) odw[wend[i].id] = i;
		if(test()) cout << "TAK\n";
		else cout << "NIE\n";
		RE(i, n) tr[pot + i] = 0;
	}	
	return 0;
}