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
#include <iostream>
#include <algorithm>
#include <memory.h>
#define REP(x,n) for(int x=0;x<(n);++x)
using namespace std;

struct CCar {
	int left;
	int top;
	int right;
	int bottom;
	int number;
	void inline match() {
		if (left>right)
			swap(left, right);
		if (top>bottom)
			swap(top, bottom);
	}
};
int w,t,n;
const int MAX_N = 50001;
CCar	auta[MAX_N];
int afterOrder[MAX_N];
int beforeOrder[MAX_N];
struct Interval_Tree {
	int w[MAX_N*4];
	int i;
	void init(int n) {
		i=1;
		while(n>i)
			i<<=1;
		for(int x=0;x<i+i;++x)
			w[x]=0;
	}
	void insert(int a, int val) {
		a+=i;
		w[a] = val;
		while(a!=1) {
			a>>=1;
			w[a] = max(w[a+a], w[a+a+1]);
		}
	}
	int query(int a, int b) {
		if (a>b)
			swap(a,b);
		a+=i;
		b+=i;
		int ret=max(w[a], w[b]);
		while((a>>1)!=(b>>1)) {
			if (~a&1)
				ret = max(ret, w[a+1]);
			if (b&1)
				ret = max(ret, w[b-1]);
			a>>=1;
			b>>=1;
		}
		return ret;
	}
} drzewo;

bool comp(const CCar& e, const CCar& f) {
	return e.left==f.left ? e.top<f.top : e.left < f.left;
}

bool zestaw() {
	cin>>n>>w;
	drzewo.init(n);
	int maks1=0, maks2=0;
  REP(x,n) {
  	auta[x].number=x;
  	cin>>auta[x].left>>auta[x].top>>auta[x].right>>auta[x].bottom;
  	auta[x].match();
  	if (maks2<(auta[x].bottom-auta[x].top)) {
  		maks2=auta[x].bottom-auta[x].top;
			if (maks2>maks1)
				swap(maks1, maks2);
  	}
  }
  sort(auta, auta+n, comp);
  REP(x,n)
		beforeOrder[auta[x].number] = x; /// auto #x siedzi teraz na pozycji beforeOrder[x]
  REP(x,n) {
  	auta[x].number=beforeOrder[x];
  	cin>>auta[x].left>>auta[x].top>>auta[x].right>>auta[x].bottom;
  	auta[x].match();
  }
  if (maks1+maks2 <= w) /// każde auta się miną
		return true;
  sort(auta, auta+n, comp);
  REP(x,n)
		afterOrder[auta[x].number] = x; /// auto X (po przestawieniu) jest w tablicy auta pod numerem afterOrder[x]
  REP(x,n) {
		if (drzewo.query(afterOrder[x],n) + (auta[afterOrder[x]].bottom-auta[afterOrder[x]].top) > w)
			return false;
		drzewo.insert(afterOrder[x], (auta[afterOrder[x]].bottom-auta[afterOrder[x]].top));
  }
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin>>t;
	REP(x,t)
		cout << (zestaw() ? "TAK" : "NIE") << endl;
	return 0;
}