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
#include <iostream>
#include <algorithm>
#include <functional>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long int LL;

class Car {
public:

	Car() {};

	static Car load(int index) {
		int position;
		int width;
		int firstX, firstY, secondX, secondY;
		cin >> firstX >> firstY >> secondX >> secondY;

		position = min(firstX, secondX);
		width = abs(firstY - secondY);
		return Car(index, position, width);
	}

	static Car mockCar(int width) {
		return Car(0, 0, width);
	}

	bool operator<(const Car & that) const {
		if(position == that.position)
			return index < that.index;
		return position < that.position;
	}

	bool isOverwhelming(int maxWidth) const {
		return width > maxWidth / 2;
	}

	void print() {
		cout << "i: " << index << ", pos: " << position << ", width: " << width << endl;
	}

	int index;
	int position;
	int width;

private:
	Car(int index, int position, int width): 
		index(index), 
		position(position),
		width(width) {}
};

bool compWidthCar(const Car & one, const Car & other) {
	return one.width < other.width;
}


int lastCollidingIndex(vector<Car> overwhelmingCars, int width, int maxWidth) {
	Car carForSearch = Car::mockCar(maxWidth - width + 1);
	auto it = lower_bound(overwhelmingCars.rbegin(), overwhelmingCars.rend(), carForSearch, compWidthCar);
	if(it == overwhelmingCars.rend())
		return -1;
	else
		return it->index;
}

function<vector<Car>(vector<Car>, Car)> accumulatingFunction(vector<int> & vec, int maxWidth) {
	return [&vec,maxWidth](vector<Car> lastOverwhelming, Car current) {
		vec[current.index-1] = lastCollidingIndex(lastOverwhelming, current.width, maxWidth);
		while(!lastOverwhelming.empty() && lastOverwhelming.back().width <= current.width)
			lastOverwhelming.pop_back();
		if(current.isOverwhelming(maxWidth))
			lastOverwhelming.push_back(current);
		return lastOverwhelming;
	};
}

bool test() {
	int carCount = 0;
	int width = 0;
	cin >> carCount >> width;
	vector<Car> carsBefore(carCount);
	vector<int> forwardBefore(carCount);
	vector<int> backwardBefore(carCount);
	vector<Car> carsAfter(carCount);
	vector<int> forwardAfter(carCount);
	vector<int> backwardAfter(carCount);
	for(int i = 0; i < carCount; ++i) {
		carsBefore[i] = Car::load(i+1);
	}

	for(int i = 0; i < carCount; ++i) {
		carsAfter[i] = Car::load(i+1);
	}

	sort(carsBefore.begin(), carsBefore.end());
	sort(carsAfter.begin(), carsAfter.end());
	accumulate(carsBefore.begin(), carsBefore.end(), vector<Car>(), accumulatingFunction(forwardBefore, width));
	accumulate(carsBefore.rbegin(), carsBefore.rend(), vector<Car>(), accumulatingFunction(backwardBefore, width));
	accumulate(carsAfter.begin(), carsAfter.end(), vector<Car>(), accumulatingFunction(forwardAfter, width));
	accumulate(carsAfter.rbegin(), carsAfter.rend(), vector<Car>(), accumulatingFunction(backwardAfter, width));

	bool ok = true;
	for(int i = 0; i < carCount; ++i) {
		if(forwardBefore[i] != forwardAfter[i] || backwardBefore[i] != backwardAfter[i])
			ok = false;
	}

	return ok;
}

int main() {
	ios_base::sync_with_stdio(0);
	int tests = 0;
	cin >> tests;
	for(int i = 0; i < tests; ++i) {
		if(test())
			cout << "TAK\n";
		else
			cout << "NIE\n";
	}
}