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
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
typedef vector<PIII> VPIII;
typedef vector<int> VI;

#define x first
#define y second
#define data first
#define id second

VPIII vals;
VI heights;
int h_parking, h_car_max;

inline void read(int na) {
	h_car_max = 0;
	heights.clear();
	vals.clear();

	heights.reserve(na);
	vals.reserve(na);

	for (int i = 0; i < na; ++i) {
		PII val;
		cin >> val.x >> val.y;
		int x2, y2;
		cin >> x2 >> y2;
		vals.push_back( PIII(val, i) );
		int h = y2 - val.y;
		heights.push_back(h);
		h_car_max = max(h_car_max, h);
	}
}

inline void collect(VI& vids) {
	vids.resize(vals.size());
	for (int i = 0; i < vals.size(); ++i) {
		vids[ vals[i].id ] = i;
		//printf("[%d](%d,%d)(%d) ", vals[i].id, vals[i].data.x, vals[i].data.y, heights[ vals[i].id ]);
	}
	//putchar('\n');
}

inline void dump(VI& vids) {
	for (int i = 0; i < vids.size(); ++i) {
		cout << vids[i] << ' ';
	}
	cout << endl;
}

VI source, target, curr;

int main() {
	int tcs;
	cin >> tcs;

	while (tcs--) {
		source.clear();
		target.clear();

		int na;
		cin >> na >> h_parking;
		//cout << na << ' ' << h_parking << endl;

		read(na);
		sort(vals.begin(), vals.end());
		collect(source);
		curr = source;

		read(na);
		sort(vals.begin(), vals.end());
		collect(target);

		//dump(source);
		//dump(target);
		//dump(curr);
		//dump(heights);

		bool ok = true;
		// this case needs check
		if ( (h_car_max << 1) > h_parking) {
			bool changed = true;
			while (ok && changed) {
				changed = false;
				for (int i = 1; ok && i < na; ++i) {
					int cid = curr[i];
					int pid = curr[i-1];

					// needs swapping?
					if ( target[pid] > target[cid] ) {
						if ( heights[cid] + heights[pid] <= h_parking ) {
							swap( curr[i-1], curr[i] );
							changed = true;
						} else { ok = false; }
					}
				} //for
				for (int i = na - 1; ok && i > 0; --i) {
					int cid = curr[i];
					int pid = curr[i-1];

					// needs swapping?
					if ( target[pid] > target[cid] ) {
						if ( heights[cid] + heights[pid] <= h_parking ) {
							swap( curr[i-1], curr[i] );
							changed = true;
						} else { ok = false; }
					}
				} //for
			} //while
			//dump(curr);
		} //if

		cout << (ok ? "TAK" : "NIE") << endl;
	}

	return 0;
}