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
program parking;

type pozycja=record
		x1,x2,y1,y2 : int64;
	 end;
	 samochod=record
		wysokosc : longint;
		pozPocz,pozKon : pozycja;
	 end;
	 tab=array [1..50002] of samochod;
	
var ustawienia : tab;
	i,j,k,t,n : integer;
	w,max : longint;
	koniec : boolean;
	
	procedure quick(od,do_ : longint);
	var i,j,x : longint;
		temp : samochod;
	begin
		i:=od;
		j:=do_;
		x:=ustawienia[(od+do_) div 2].wysokosc;
		repeat
			while ustawienia[i].wysokosc>x do inc(i);
			while x>ustawienia[j].wysokosc do dec(j);
			if i<=j then begin
				temp:=ustawienia[i];
				ustawienia[i]:=ustawienia[j];
				ustawienia[j]:=temp;
				inc(i);
				dec(j);
			end;
		until i>j;
		if od<j then quick(od,j);
		if i<do_ then quick(i,do_);
	end;

begin
	readln(t);
	for i:=1 to t do begin
		read(n);
		readln(w);
		for j:=1 to n do begin
			read(ustawienia[j].pozPocz.x1);
			read(ustawienia[j].pozPocz.y1);
			read(ustawienia[j].pozPocz.x2);
			readln(ustawienia[j].pozPocz.y2);
			ustawienia[j].wysokosc:=ustawienia[j].pozPocz.y2-ustawienia[j].pozPocz.y1;
		end;
		for j:=1 to n do begin
			read(ustawienia[j].pozKon.x1);
			read(ustawienia[j].pozKon.y1);
			read(ustawienia[j].pozKon.x2);
			readln(ustawienia[j].pozKon.y2);
		end;
		quick(1,n);
		j:=1;
		max:=ustawienia[j].wysokosc;
		koniec:=false;
		while (not koniec)and(ustawienia[j].wysokosc+max>w)and(j<=n) do begin
			k:=j+1;
			while (not koniec)and(ustawienia[j].wysokosc+ustawienia[k].wysokosc>w)and(k<=n) do begin
				if ((ustawienia[k].pozPocz.x1>=ustawienia[j].pozPocz.x2)and
				   (ustawienia[k].pozKon.x1<ustawienia[j].pozKon.x2))or
				   ((ustawienia[j].pozPocz.x1>=ustawienia[k].pozPocz.x2)and
				   (ustawienia[j].pozKon.x1<ustawienia[k].pozKon.x2)) then
						koniec:=true;
				inc(k);
			end;
			inc(j);
		end;
		if koniec then writeln('NIE')
		else writeln('TAK');
	end;
end.