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

type
  tab = array[1..50000, 1..3] of longword;

var
  m,i1 : byte;
  n : word;
  w : longword;
  a : array[1..50000, 1..3] of longword;

  i,j,k : word;

  tmp1,tmp2,tmp3,tmp4 : longword;
  NO : boolean;

procedure qsort(var t:tab; l,r:longword);
var
  p,tmp : longword;
  i,j : longword;
  begin
    i:=l; j:=r;
    tmp:=(l+r) div 2;
    p:=t[tmp,1];
    repeat
      while t[i,1]<p do i:=i+1;
      while p<t[j,1] do j:=j-1;
      if i<=j then
      begin
        tmp:=t[i,1]; t[i,1]:=t[j,1]; t[j,1]:=tmp;
        tmp:=t[i,2]; t[i,2]:=t[j,2]; t[j,2]:=tmp;
        tmp:=t[i,3]; t[i,3]:=t[j,3]; t[j,3]:=tmp;
        i:=i+1; j:=j-1
      end
    until i>=j;
    if l<j then qsort(t,l,j);
    if i<r then qsort(t,i,r)
  end;

begin
  readln(m);

  for i1:=1 to m do
  begin
    NO:=false;
    readln(n,w);
    if n>1 then
    begin
      for i:=1 to n do
      begin
        readln(tmp1,tmp2,tmp3,tmp4);
	if tmp4>tmp2 then a[i,1]:=tmp4-tmp2
          else a[i,1]:=tmp2-tmp4;
        if tmp3>tmp1 then a[i,2]:=tmp1
        else a[i,2]:=tmp3
      end;
      for i:=1 to n do
      begin
        readln(tmp1,tmp2,tmp3,tmp4);
        if tmp3>tmp1 then a[i,3]:=tmp1
        else a[i,3]:=tmp3
      end;
      qsort(a,1,n);
      i:=n; j:=1;
      repeat
        tmp1:=w-a[i,1];
        while (a[j,1]<=tmp1) and (j<i) do
          j:=j+1;
        if (j<i) then
        begin
          k:=j;
          repeat
            if ((a[i,2]>a[k,2]) and (a[i,3]>a[k,3])) or ((a[i,2]<a[k,2]) and (a[i,3]<a[k,3]))
              then k:=k+1
            else NO:=true
          until (k>=i) or NO
        end;
	i:=i-1;
       until NO or (i<j)
    end;
    if NO then writeln('NIE') else writeln('TAK')
  end;
end.