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
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;


struct Auto {
	long long pocz;
	long long wys;
	long long koniec;
}; 
typedef vector< Auto > parking_t;

void wczytaj_dane( int ile_aut, parking_t& parking )
{
	parking.resize(ile_aut);
	for( int i = 0; i < ile_aut; ++i ) {
		long long x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		parking[i].pocz = min(x1, x2);
		parking[i].wys = abs(y2 - y1);
	}
	for( int i = 0; i < ile_aut; ++i ) {
		long long x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		parking[i].koniec = min(x1,x2);
	}
}

struct Mijacz {
	long long wys;
	Mijacz(long long wys) : wys(wys) {};
	bool operator() (Auto const& a, Auto const& b)
	{
		return a.wys + b.wys <= wys;
	}
};

bool parkuj( parking_t& parking, Mijacz mijacz )
{
	int do_przestawienia = parking.size();
	if( do_przestawienia < 2 ) return true;

	sort( parking.begin(), parking.end(), [](Auto const&a, Auto const& b) {
		return a.pocz < b.pocz;
	});

	bool dalej = true;
	while ( dalej ) {
		dalej = false;
		for( int i = 1; i < do_przestawienia; ++i ) {
			auto& a = parking[i-1];
			auto& b = parking[i];
			if( a.koniec > b.koniec) {
				if( mijacz( a, b ) ) {
					swap(parking[i-1], parking[i]);
					dalej = true;
				}
				else {
					return false;
				}
			}
		}; 
		do_przestawienia -= 1;
	}
	return true;
}

bool rozwiaz() 
{
	long long ile_aut, wys;
	cin >> ile_aut >> wys;
	parking_t parking;

	wczytaj_dane( ile_aut, parking );
	Mijacz mijacz(wys);
	bool odp = parkuj( parking, mijacz );
	return odp;
}

int main()
{
	int ile_testow;
	ios_base::sync_with_stdio( false );
	cin >> ile_testow;

	string odp;
	for( int i = 0; i < ile_testow; ++i )
	{
		odp += (rozwiaz()? "TAK\n" : "NIE\n" );
	}
	cout << odp;
}