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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
int tree[4194304], from[4194304], to[4194304];

int get_max_node(int node, int a, int b) {
if (a<=from[node] && to[node] <= b)
return tree[node];
if (b<from[node] || a>to[node]) return 0;

int l = 2*node;
//printf("%d %d\n", to[l], from[l+1]);
if (b<from[l] || a>to[l]) return get_max_node(l+1, a, b);
else if (b<from[l+1] || a>to[l+1]) return get_max_node(l, a, b);
else return max(get_max_node(l, a,to[l]), get_max_node(l+1,from[l+1], b));
}

int get_max(int a, int b) {
return get_max_node(1, a, b);
}

int main() {
int t;
scanf("%d", &t);
while (t--) {
long long n, w;
vector< pair<int, int> > v;
scanf("%lld %lld", &n, &w);
int heights[n+2];
for (int i=0;i<n;i++){
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
int h = y2>y1 ? y2-y1 : y1-y2;
v.push_back(make_pair(min(x1, x2), i));
heights[i] = h;
}
sort(v.begin(), v.end());
int mapa[n+2];
for (int i=0;i<n;i++) mapa[v[i].second] = i+1;

v.clear();
for (int i=0;i<n;i++){
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
//int h = y2>y1 ? y2-y1 : y1-y2;
v.push_back(make_pair(min(x1,x2), i));
}
sort(v.begin(), v.end());
int koniec[n+2];
for (int i=0;i<n;i++) koniec[i+1] = mapa[v[i].second];

//for (int i=0;i<n;i++) printf ("%d (%d): %d\n", i, heights[i], mapa[i]);
//for (int i=0;i<n;i++) printf("%d ", mapa[i]); printf("\n");
//for (int i=1;i<=n;i++) printf("%d ", koniec[i]); printf("\n");

int size = 1;
int s = 1;
int tmp = n;
while (tmp>1) {
tmp = tmp/2+ (tmp%2);
s *= 2;
size += s;
}
int org_size = size;
size++;
for (int i=0;i<size+5;i++) {tree[i]=0; from[i]=1; to[i]=n;}
size /= 2;
int pozycja[n+4];
for (int i=0;i<n;i++) pozycja[mapa[i]] = i;
//printf("Pozycja: ");for (int i=1;i<=n;i++) printf("%d ", pozycja[i]); printf("\n");
for (int i=0;i<n;i++) {
tree[size+i] = heights[pozycja[i+1]];
to[size+i] = from[size+i] = i+1;
}
while (size >0){
size /= 2;
s /= 2;
for (int i=0;i<s;i++) {tree[size+i] = max(tree[2*(size+i)], tree[2*(size+i)+1]);
//printf("%d = max(%d, %d)\n",size+i, 2*(size+i), 2*(size+i)+1);
from[size+i] = from[2*(size+i)];
to[size+i] = to[2*(size+i)+1];
//printf("%d ~ [%d, %d]\n",size+i, from[size+i], to[size+i]);
}
}
bool result = true;

for (int i=n;i>0;i--) {
// sprawdzić
if (koniec[i] != n && get_max(koniec[i]+1, n) + heights[pozycja[koniec[i]]] > w) {result = false; 
//printf ("NIE: %d (%d)\n", koniec[i], get_max(koniec[i]+1, n)); 
break;}
// usunąć koniec[i]
size = (org_size + 1)/2;
int pos = size+koniec[i]-1;
tree[pos] = 0;
pos /=2;
while(pos>0) {
tree[pos] = max(tree[2*pos], tree[2*pos+1]); pos /=2;
}
}

printf("%s\n", result ? "TAK" : "NIE");

}
return 0;
}