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
#include <algorithm>
#include <cstdio>
#include <cstring>

const int d = 1<<16;
const int size = d<<1;
const int bitsize = size<<2;
struct MT
{
	int T[size];
	void set(int pos,int val);
	int get(int l,int r);
}mt;

int n,w;
int X[d],W[d];
int S[d],rS[d],D[d];


int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		std::memset(mt.T,bitsize,'0');
		scanf("%d%d",&n,&w);
		for(int i = 1,x1,y1,x2,y2; i <= n; ++i)
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			X[i] = std::min(x1,x2);
			W[i] = std::abs(y2-y1);
			S[i] = D[i] = i;
		}
		std::sort(S+1,S+n+1,[&](int i,int j)->bool
		{
			return X[i] < X[j];
		});
		for(int i = 1; i <= n; ++i)
		{
			mt.set(i,W[S[i]]);
			rS[S[i]] = i;
		}
		
		for(int i = 1,x1,x2; i <= n; ++i)
		{
			scanf("%d%*d%d%*d",&x1,&x2);
			X[i] = std::min(x1,x2);
			
		}
		std::sort(D+1,D+n+1,[&](int i,int j)->bool
		{
			return X[i] < X[j];
		});
		
		
		bool ok = true;
		for(int i = 1,k; ok && i <= n; ++i)
		{
			k = rS[D[i]];
			mt.set(k,0);
			if(mt.get(1,k) + W[D[i]] > w) ok = false;
		}
		
		if(ok) puts("TAK");
		else puts("NIE");
	}
	return 0;
}

void MT::set(int pos,int val)
{
	T[pos += d] = val;
	while((pos>>=1))
		T[pos] = std::max(T[pos<<1],T[(pos<<1) +1]);
}

int MT::get(int l,int r)
{
	int res = 0;
	l += d,r += d;
	while(l < r)
	{
		if((l&1)) { res = std::max(res,T[l]); l = (l>>1) + 1;}
		else l >>= 1;
		if(!(r&1)) { res = std::max(res,T[r]); r = (r>>1) - 1;}
		else r >>= 1;
	}
	if(l == r)
		res = std::max(res,T[l]);
	return res;
}