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
#include<cstdio>
#include<vector>
#include<algorithm>
#define MP make_pair
#define fi first
#define se second
using namespace std;
const int base = 65536, N = 50000;
int z, n, w, i, x1, x2, yy, y2, maxh, pozp[N], h[N], t[2 * base];
bool e;
vector<pair<int, int> >v;

void del(int x)
{
  x += base;
  t[x] = 0;
  x /= 2;
  while(x > 0)
  {
    t[x] = max(t[x * 2], t[x * 2 + 1]);
    x /= 2;
  }
}

int query(int x)
{
  int w = 0;
  x += base;
  while(x > 1)
  {
    if (x % 2 == 1){w = max(w, t[x - 1]);}
    x /= 2;
  }
  return w;
}

int main()
{
  scanf("%d", &z);
  
  while(z--)
  {
    scanf("%d%d", &n, &w);
    
    for(i = 0; i < n; i++)
    {
      scanf("%d%d%d%d", &x1, &yy, &x2, &y2);
      v.push_back(MP(min(x1, x2), i));
      h[i] = abs(y2 - yy);
    }
    
    sort(v.begin(), v.end());
    
    for(i = 0; i < v.size(); i++)
    {
      t[i + base] = h[v[i].se];
      pozp[v[i].se] = i;
    }
    i = base - 1;
    while(i > 0)
    {
      t[i] = max(t[i * 2], t[i * 2 + 1]);
      i--;
    }
    
    v.clear();
    for(i = 0; i < n; i++)
    {
      scanf("%d%d%d%d", &x1, &yy, &x2, &y2);
      v.push_back(MP(min(x1, x2), i));
    }
    
    sort(v.begin(), v.end());
    
    e = true;
    
    for(i = 0; i < v.size(); i++)
    {
      maxh = query(pozp[v[i].se]);
      if (maxh + h[v[i].se] > w){printf("NIE\n");e = false;break;}
      del(pozp[v[i].se]);
    }
    if (e == true){printf("TAK\n");}
    v.clear();
  }
  
return 0;
}