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
#include<iostream>
#include<vector>
#include<sstream>
#include<algorithm>
#include<cmath>

using namespace std;

struct Car {

	const int x0, y0;
	const int width, height;
	const int car_no;

	Car(int _x0, int _y0, int _width, int _height, int _car_no) :
		x0(_x0), y0(_y0), width(_width), height(_height), car_no(_car_no) {}
};

Car* const CAN_NOT_MOVE = new Car(-1, -1, -1, -1, -1);


Car* create(int x1, int y1, int x2, int y2, int _idx) {
	int _x0 = min(x1, x2);
	int _y0 = min(y1, y2);

	int _width = max(x1, x2) - _x0;
	int _height = max(y1, y2) - _y0;

	return new Car(_x0, _y0, _width, _height, _idx);
}

bool is_common(int x0, int x1, int y0, int y1) {
	// make sure x0 <= y0
	if(x0 > y0) {
		int a, b;
		a = x0; b = x1;
		x0 = y0; x1 = y1;
		y0 = a; y1 = b;
	}
	return x0 < y0 && y0 < x1;
}

// c1 < c2
// to order the cars
bool gt(Car* c1, Car* c2) {
	return (c1)->x0 < (c2)->x0 ||
		( (c1)->y0 < (c2)->y0 &&
		  is_common((c1)->x0, (c1)->width, (c2)->x0, (c2)->width)
		);
}

void read_cars(vector<Car*>& cars) {
	int i = 0;
	for(auto it = cars.begin(); it != cars.end(); it++, i++) {
		int x1, y1,
		    x2, y2;

		cin >> x1 >> y1 >> x2 >> y2;
		*it = create(x1, y1, x2, y2, i);
	}
}

void init_where_to_go(vector<int>& where_to_go, vector<Car*>& expected_cars) {
	int i = 0;
	for(auto it = expected_cars.begin(); it != expected_cars.end(); it++, i++) {
		where_to_go[(*it)->car_no] = i;
	}
}

int sign(int v) {
	if(v < 0) return -1;
	return 1;
}

Car* move_car(Car* car, int car_idx, int goto_idx, vector<Car*>& start_points, int const height_constraint) {

	int dist = goto_idx - car_idx;
	int direct = sign(dist);
	dist = abs(dist);
	if(dist == 0) {
		return car;
	}
	for(int i = car_idx + direct; abs(i - car_idx) <= dist; i += direct) {
		Car* passing = start_points[i];
		if (passing != NULL &&
			(((long)passing->height) + ((long)car->height) > ((long)height_constraint))
			) {

			return CAN_NOT_MOVE;
		}
	}
	Car* swp = start_points[goto_idx];
	start_points[goto_idx] = car;
	car = swp;
	return car;
}

bool is_it_possible_to_arange(vector<Car*>& start_points, vector<int>& where_to_go, int const height_constraint) {

	for(auto sp = start_points.begin(); sp != start_points.end(); sp++) {
		Car* car = *sp;
		int goto_idx = where_to_go[car->car_no];
		int car_idx = distance(start_points.begin(), sp);
		if(goto_idx != car_idx) {
			*sp = NULL;
			while(car != NULL) {
				goto_idx = where_to_go[car->car_no];
				car = move_car(car, car_idx, goto_idx, start_points, height_constraint);
				if(car == CAN_NOT_MOVE) {
					return false;
				}
				car_idx = goto_idx;
			}
		}
	}
	return true;
}


int main() {
	int t;
	cin >> t;
	for(int i = 0; i < t; i++) {
		int n, // 1 <= n <= 50 000
		    w; // 1 <= w <= 10^9
		cin >> n >> w;

		vector<Car*> start_points(n);

		read_cars(start_points);

		sort(start_points.begin(), start_points.end(), gt);

		vector<Car*> expected_cars(n);
		read_cars(expected_cars);

		sort(expected_cars.begin(), expected_cars.end(), gt);

		//map: car_no -> expected position
		vector<int> where_to_go(n);
		init_where_to_go(where_to_go, expected_cars);

		bool answer = is_it_possible_to_arange(start_points, where_to_go, w);
		cout << (answer ? "TAK" : "NIE") << endl;
	}
	return 0;
}