Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8. Możesz pobrać ten plik i spróbować otworzyć go samodzielnie. 
  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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define st first
#define nd second
#define REF &

typedef pair<int,int> pii;
typedef vector<int> vi;

#define REP(i,n) for(int i = 0; i < n; ++i) 
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)

template<typename T>
class drzewo_przedzialowe_tablicowe{
	private:
		int pot2;				// pierwsza pot�ga dw�jki wi�ksza r�wna ni� tab.size()
		vector<T> drz;			// drzewo
		T (*f)(T,T);			// ��czne f
		T e;					// f(e, x) = x
	public:
		drzewo_przedzialowe_tablicowe(vector<T> REF tab, T (*__f)(T,T), T __e){
			f = __f;
			e = __e;
			
			pot2 = 1;
			while(pot2 <= tab.size()) pot2 *= 2;
			drz.resize(2*pot2);
			REP(i,tab.size()) drz[pot2 + i] = tab[i];
			FOR(i,tab.size(),pot2-1) drz[pot2 + i] = e;
			FORD(i,pot2-1,1) drz[i] = f(drz[2*i], drz[2*i+1]);
		}
		void wstaw(T elem, int i){
			i += pot2;
			drz[i] = elem;
			for(i /= 2; i; i /= 2) drz[i] = f(drz[2*i], drz[2*i+1]);
		}
		T zapytanie(int a, int b){
			if(a > b) return e;
			a += pot2;
			b += pot2;
			T wynl = e, wynp = e;
			while(a < b){
				if(a & 1) {wynl = f(wynl, drz[a]); ++a;}		// je�li a jest prawym dzieckiem
				if(!(b & 1)) {wynp = f(drz[b], wynp); --b;}		// je�li b jest lewym dzieckiem
				a /= 2;
				b /= 2;
			}
			if(a == b) wynl = f(wynl,drz[a]);
			return f(wynl, wynp);
		}
};

const int minf = -1000*1000*1000 - 9;

int maks(int a, int b){ return max(a,b);}

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		int n, w;
		scanf("%d%d",&n,&w);
		vector<pii> a(n), b(n);
		vi ha(n), hb(n);
		for(int i = 0; i < n; ++i){
			int x1,y1,x2,y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			a[i] = pii(x1,i);
			ha[i] = abs(y1-y2);
		}
		for(int i = 0; i < n; ++i){
			int x1,y1,x2,y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			b[i] = pii(x1,i);
			hb[i] = abs(y1-y2);
		}
		//swap(a,b); swap(ha, hb);
		sort(a.begin(), a.end());		
		sort(b.begin(), b.end());	
		
		//for(int i = 0; i < a.size(); ++i) printf("%d %d\n", a[i].st , a[i].nd);	puts("\n");
		//for(int i = 0; i < b.size(); ++i) printf("%d %d\n", b[i].st , b[i].nd);	puts("\n");
		
		
		vi p(n);
		for(int i = 0; i < n; ++i) p[a[i].nd] = i;
		for(int i = 0; i < n; ++i){
			a[i].st = ha[a[i].nd];
			b[i].st = hb[b[i].nd];
			a[i].nd = p[a[i].nd];
			b[i].nd = p[b[i].nd];
		}
		/*
		printf("%d\n", w);
		for(int i = 0; i < n; ++i)
			for(int k = 0; k < n; ++k)
				if(i < k and b[i].nd < b[k].nd and b[i].st + b[k].st > w) puts("xxxxxxxxxxxxxxxxx");
		*/
		//for(int i = 0; i < a.size(); ++i) printf("%d %d\n", a[i].st , a[i].nd);	puts("\n");
	//	for(int i = 0; i < b.size(); ++i) printf("%d %d\n", b[i].st , b[i].nd);	puts("\n");
		
		vector<int> v(n+9, minf);
		drzewo_przedzialowe_tablicowe<int> d(v, maks, minf);
		bool fail = 0;
		for(int i = n; i--;){
			int mojeh = b[i].st;
			int wys =   b[i].nd;
			int maxh = d.zapytanie(0, wys);
			if(maxh + mojeh > w) { 			//	printf("%d %d %d\n", mojeh, wys, maxh);
				fail = 1;
				break; 
			}
			d.wstaw(mojeh, wys);
		}
		puts(fail ? "NIE" : "TAK");
	}
	return 0;
}