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


struct Tree { 
	int v,w; 
} drz[MAXN];

void insert(int OD, int DO, const int &from, const int &to, const int &c, int v){
	if(from<=OD&&to>=DO) drz[v].v=c;             
	else{
		int a = (OD+DO)/2;
		if(from<=a) insert(OD,a,from,to,c,v*2);   
		if(to>a) insert(a+1,DO,from,to,c,v*2+1);
		drz[v].w = max(drz[v*2].w+drz[v*2].v,drz[v*2+1].w+drz[v*2+1].v);
	}
}

int query(int OD, int DO, int from, int to, int v, int s){ 
	if(from<=OD && to>=DO) return s+drz[v].v+drz[v].w;             
	int a,res=0;
	a=(OD+DO)/2;
	if(from<=a) res=max(res,query(OD,a,from,to,v*2,drz[v].v+s));   
	if(to>a) res=max(res,query(a+1,DO,from,to,v*2+1,drz[v].v+s));
	return res;
}

int z,n,w;

struct car {
	int i,h,x1,x2;
	bool operator < (const car &c) const {
		return x1 < c.x1;
	}
} X[MAXN],Y[MAXN];


int main()
{
	scanf("%d",&z);
	while(z--) 
	{
		int h1,h2;
		scanf("%d %d",&n,&w);
		for(int i=0;i<n;i++) {
			scanf("%d %d %d %d",&X[i].x1, &h1, &X[i].x2, &h2);
			if(X[i].x1 > X[i].x2) swap(X[i].x1, X[i].x2);
			X[i].h = max(h2-h1, h1-h2);
		}
		for(int i=0;i<n;i++) {
			scanf("%d %d %d %d",&Y[i].x1, &h1, &Y[i].x2, &h2);
			if(Y[i].x1 > Y[i].x2) swap(Y[i].x1, Y[i].x2);
			Y[i].h = max(h2-h1, h1-h2);
		}
		for(int i=0;i<n;i++) X[i].i = Y[i].i = i;
		
		sort(X,X+n);
		for(int i=0;i<n;i++) Y[X[i].i].i = i;
		sort(Y,Y+n);
		for(int i=0;i<n;i++) X[Y[i].i].i = i;
		for(int i=0;i<n;i++) insert(0,n,i,i,X[i].h,1);
		bool res = true;
		
		for(int i=0;i<n;i++) {
			int pos = Y[i].i;
			insert(0,n,pos,pos,0,1);
			
			if(pos == 0) continue;
			int h = query(0,n,0,pos-1,1,0);
			
			if(h + X[pos].h > w) {
				res = false;
				break;
			}
		}
		printf(res ? "TAK\n" : "NIE\n");
	}
	return 0;
}