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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#define NDEBUG
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <utility>
using namespace std;
#define TRACE(x) cerr<<"# "#x<<endl;
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<endl;
typedef unsigned long long ULL;
typedef long long LL;
const int INF = 0x7FFFFFFF;

struct Car {
	int w, p, k, i;

	Car(int w, int p): w(w), p(p) {}
};


void disp(const char * title, vector<Car> &v) {
	fprintf(stderr, " DISPLAY %s: \n", title);
	for( Car &c : v) {
		fprintf(stderr, "   i = %d\tp = %d\tk = %d\t w = %d\n", c.i, c.p, c.k, c.w);
	}
	fprintf(stderr, "-------------------\n\n");	
};

int main() {
	int t, n, w;
	int x1, y1, x2, y2;
	vector<Car> v, v_tmp;

	scanf("%d", &t);

	for(int tt=0; tt<t ;++tt) {
		scanf("%d %d", &n, &w);
		v_tmp.clear();
		v_tmp.reserve(n+1);
		v.clear();
		v.reserve(n+1);

		for(int i=0; i<n ;++i) {
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
				// jesli x1 > x2 lub y1 > y2 
				x1 = min(x1, x2);
				int wys = y2 - y1;
				if(y1 > y2) wys = y1 - y2;
			v_tmp.emplace_back( Car(wys, x1) );
		}

		for( Car &c : v_tmp) {
			scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
			c.k = x1;
		}

	#if 1
		// OPTYMALIZACJA - poczatek
		
		// sortuj wedlug kolejnosci na starcie
		sort(v_tmp.begin(), v_tmp.end(), [](const Car &a, const Car &b) -> bool { return (a.p < b.p); });


		// numeruj
		int index = 0;
		for( Car &c : v_tmp) {
			c.i = ++index;
		}

//disp("na starcie", v_tmp);

		// sortuj wedlug kolejnosci na koncu
		sort(v_tmp.begin(), v_tmp.end(), [](const Car &a, const Car &b) -> bool { return (a.k < b.k); });

//disp("na koncu", v_tmp);

		// pomijaj nieprzestawione podciagi (zastap podciag jednym najwyzszym)
		auto last = v_tmp.end() - 1;
		for(auto a=v_tmp.begin(); a<=last ;) {

//			cerr << " FOR a  i = " << a->i << endl;
			
			int w_max = a->w;
			index = a->i ;
			auto b = a+1;
			for(; b<=last ;++b) {
			
//				cerr << "   FOR b  i = " << b->i << endl;

				if(b->i != ++index) {
					break;
				} else {
					if(b->w > w_max) {
						w_max = b->w;
					}
				}
			}
			
			a->w = w_max;
			v.emplace_back( *a );

			a = b;
		}
//disp("zoptymalizowane", v);
		
		// OPTYMALIZACJA - koniec
	#else
		auto last = v_tmp.end();
		v = v_tmp;
	#endif

		sort(v.begin(), v.end(), [](const Car &a, const Car &b) -> bool { return (a.w > b.w); });

//fprintf(stderr, "%lu  ", v.size());
		
		last = v.end() - 1;
		
		if((v.size() < 2) || ((v.at(0).w + v.at(1).w) <= w)) {
// uncomment below !!!
// uncomment below !!!
			goto YES;
		}

		for(auto a=v.begin(); a<last ;++a) {
			for(auto b=a+1; b<=last ;++b) {
				if((a->w + b->w) > w) {
					if( ((a->p < b->p) && (a->k > b->k)) ||
					    ((a->p > b->p) && (a->k < b->k)) ) {
						goto NO;
					}
				} else {
// uncomment below !!!
// uncomment below !!!
					break;
				}
			}
		}


		YES:
		printf("TAK\n");
		continue;

		NO:
		printf("NIE\n");
	}	
	
	return 0;
}