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
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 65536
using namespace std;

vector<pair<int, int> > linia, koniec;
pair<pair<int, int>, pair<int, int> > najpierw[50000], potem[50000];
vector<int> drzewo;
int n, w, maksimum;
int miejsce[50000];

int wb(int x)
{
    if(x>=0) return x;
    else return -x;
}
int maks(int x)
{
    if(x<N) drzewo[x]=max(maks(x*2), maks(x*2+1));
    return drzewo[x];
}

void najw(int a, int b, int v, int p, int q)
{
    if(a==p && b==q)
    {
        maksimum=max(maksimum, drzewo[v]);
        return;
    }
    int m=(p+q)/2;
    if(b<=m) najw(a, b, v*2, p, m);
    else if(a>=m) najw(a, b, v*2+1, m, q);
    else
    {
        najw(a, m, v*2, p, m);
        najw(m, b, v*2+1, m, q);
    }
}

int main()
{
    int t, n, w, x1, x2, y1, y2;
    scanf("%d", &t);
    for(int i=0; i<t; i++)
    {
        bool czy_mozna=true;
        drzewo.resize(2*N+1);
        scanf("%d%d", &n, &w);
        for(int j=0; j<n; j++)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            linia.push_back(make_pair(min(x1, x2), j));
            najpierw[j]=make_pair(make_pair(x1, y1), make_pair(x2, y2));
        }
        sort(linia.begin(), linia.end());
        for(int j=0; j<n; j++)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            koniec.push_back(make_pair(min(x1, x2), j));
            potem[j]=make_pair(make_pair(x1, y1), make_pair(x2, y2));
        }
        sort(koniec.begin(), koniec.end());
        for(int j=0; j<koniec.size(); j++) miejsce[koniec[j].second]=j;
        for(int j=0; j<linia.size(); j++)
        {
            najw(N+miejsce[linia[j].second], 2*N+1, 1, N, 2*N+1);
            if(maksimum+wb(najpierw[linia[j].second].first.second-najpierw[linia[j].second].second.second)>w)
            {
                czy_mozna=false;
                break;
            }
            else
            {
                drzewo[N+miejsce[linia[j].second]]=max(wb(najpierw[linia[j].second].first.second-najpierw[linia[j].second].second.second),drzewo[N+miejsce[linia[j].second]]);
                maks(1);
            }
            maksimum=0;
        }
        if(czy_mozna) printf("TAK\n");
        else printf("NIE\n");
        drzewo.clear();
        linia.clear();
        koniec.clear();
        maksimum=0;
    }
}