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 <bits/stdc++.h>
//#include <emmintrin.h>

using namespace std;

#define FORE(it,c)  for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define FOR(i,a,b)  for(int i=(a);i<(b);++i)
#define REP(i,a)    FOR(i,0,a)
#define ZERO(m)    memset(m,0,sizeof(m))
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define S          size()
#define LL          long long
#define ULL        unsigned long long
#define LD          long double
#define MP          make_pair
#define X          first
#define Y          second
#define VC          vector
#define PII        pair <int, int>
#define VI          VC < int >
#define VVI        VC < VI >
#define VD          VC < double >
#define VVD        VC < VD >
#define VS          VC < string >
#define DB(a)      cerr << #a << ": " << (a) << endl;

template<class T> void print(VC < T > v) {cerr << "[";if (v.S) cerr << v[0];FOR(i, 1, v.S) cerr << ", " << v[i];cerr << "]\n";}
template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
VS splt(string s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < s.S) all.PB(s.substr(p)); return all;}

const int MAXN = 50000;
int h[MAXN];
int pos1[MAXN];
int pos2[MAXN];
int order1[MAXN];
int order2[MAXN];
PII vp[MAXN];
int bit[1<<17];

int main() {
	int tc;
	cin >> tc;
	while (tc--) {
		int n, w;
		cin >> n >> w;
		
		REP(i, n) {
			int x1,y1,x2,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			if (x1 > x2) swap(x1, x2);
			if (y1 > y2) swap(y1, y2);
			vp[i] = MP(x1, i);
			h[i] = y2 - y1;
		}
		sort(vp, vp + n);
		REP(i, n) {
			order1[i] = vp[i].Y;
			pos1[vp[i].Y] = i;
		}
		
		REP(i, n) {
			int x1,y1,x2,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			if (x1 > x2) swap(x1, x2);
			if (y1 > y2) swap(y1, y2);
			vp[i] = MP(x1, i);
		}
		sort(vp, vp + n);
		REP(i, n) {
			order2[i] = vp[i].Y;
			pos2[vp[i].Y] = i;
		}
		
		ZERO(bit);
		REP(i, n) bit[(1<<16)+i] = h[order1[i]];
		for (int i = (1<<16)-1; i; i--) bit[i] = max(bit[i+i],bit[i+i+1]);
		
		bool ok = true;
		
		REP(i, n) {
			int id = order2[i];
			int op = (1<<16)+pos1[id];
			int p;
			
			p = op;
			bit[p] = 0;
			while (p > 1) {
				p >>= 1;
				bit[p] = max(bit[p+p], bit[p+p+1]);
			}
			
			int mh = 0;
			p = op;
			while (p > 1) {
				if (p & 1) mh = max(mh, bit[p-1]);
				p >>= 1;
			}
			
			ok &= mh + h[id] <= w;
		}
		
		cout << (ok ? "TAK" : "NIE") << endl;
	}
	return 0;
}