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
148
149
150
151
152
//Autor: Mateusz Wasylkiewicz
//Zawody: Potyczki Algorytmiczne 2014
//Strona: http://potyczki.mimuw.edu.pl/
//Zadanie: Parking, runda 3B
//Czas: O(t*n*log(n))
//Opis:
//	Sortuje samochody w kolejnosci od lewej do prawej po ich docelowym miejscu, wzgledem
//	wspolrzednej x lewego brzegu. W takiej kolejnosci przeparkowuje samochody na lewo, o ile to
//	mozliwe. W.p.p. parkowanie jest niemozliwe. Samochod da sie przeparkowac na lewo iff miesci sie
//	z kazdym innym samochodem lezacym na lewo od niego na parkingu na wysokosc. Sprawnie
//	implementuje sprawdzanie, czy przeparkowanie jest mozliwe przy pomocy drzewa przedzialowego.
#include <algorithm>
#include <iostream>
using namespace std;

#define FOR(x, a, b) for (int x = (a); x <= (b); x++)
#define FORD(x, a, b) for (int x = (a); x >= (b); x--)
#define REP(x, n) for (int x = 0; x < (n); x++)

struct Samochod
{
	int wsk, x, h; //wsk - indeks tego samochodu w przeciwnej tablicy
			//x - wspolrzedna x lewego brzegu, h - wysokosc samochodu
	
	inline bool operator < (const Samochod& dane) const
	{
		return x < dane.x;
	}
	
	inline void wczytaj(int numer)
	{
		wsk = numer;
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x = min(x1, x2);
		h = max(y1, y2) - min(y1, y2);
	}
};

const int MAX_N = 50010; //maksymalna ilosc samochodow
int n, w; //n - liczba samochodow na parkingu, w - wysokosc parkingu
Samochod sam[MAX_N]; //sam[i] - poczatkowe polozenie jednego z samochodow
Samochod miejsce[MAX_N]; //miejsce[i] - koncowe polozenie jednego z samochodow

namespace D
{
	const int H = 16; //H - wysokosc drzewa
	const int ILE = 1 << H;
	int d[2*ILE];
	
	inline void zbuduj_drzewo()
	{
		FOR(i, ILE, 2*ILE-1)
			d[i] = 0;
		REP(i, n)
			d[i + ILE] = sam[i].h;
		FORD(i, ILE-1, 1)
			d[i] = max(d[2*i], d[2*i+1]);
	}
	
	//Zmienia wartosc elementu a na c.
	inline void zmien(int a, int c)
	{
		a += ILE;
		d[a] = c;
		a /= 2;
		while (a >= 1)
		{
			d[a] = max(d[2*a], d[2*a+1]);
			a /= 2;
		}
	}
	
	//Zwraca maksimum z wartosci elementow z przedzialu [a..b].
	inline int maksimum(int a, int b)
	{
		a += ILE;
		b += ILE;
		int wynik = max(d[a], d[b]), va = a / 2, vb = b / 2;
		while (va != vb)
		{
			if (a % 2 == 0)
				wynik = max(wynik, d[a + 1]);
			if (b % 2 == 1)
				wynik = max(wynik, d[b - 1]);
			
			a = va;
			b = vb;
			va /= 2;
			vb /= 2;
		}
		return wynik;
	}
}

void wczytaj_dane()
{
	cin >> n >> w;
	REP(i, n)
		sam[i].wczytaj(i);
	REP(i, n)
		miejsce[i].wczytaj(i);
}

void posortuj()
{
	sort(miejsce, miejsce + n);
	REP(i, n)
	{
		int nr = miejsce[i].wsk;
		sam[nr].wsk = i;
	}
	
	sort(sam, sam + n);
	REP(i, n)
	{
		int pom = sam[i].wsk;
		miejsce[pom].wsk = i;
	}
}

//Zwraca true iff da sie przeniesc samochod numer nr skrajnie na lewo parkingu.
//Jesli da sie, usuwa ten samochod z parkingu.
inline bool ustaw(int nr, int h)
{
	int maks = (nr == 0 ? 0 : D::maksimum(0, nr - 1));
	if (maks + h > w)
		return false;
	D::zmien(nr, 0);
	return true;
}

bool zrob_test()
{
	wczytaj_dane();
	posortuj();
	D::zbuduj_drzewo();
	REP(i, n)
		if (! ustaw(miejsce[i].wsk, miejsce[i].h))
			return false;
	return true;
}

int main()
{
	ios_base::sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--)
		cout << (zrob_test() ? "TAK\n" : "NIE\n");
	return 0;
}