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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct Car {
    int x;
    int w;
    int i;
    int ind;
    int left;
    int right;
};

bool compX(Car i, Car j) {
    return i.x < j.x;
}

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const Car& lhs, const Car&rhs) const
  {
    if (reverse) return (lhs.w>rhs.w);
    else return (lhs.w<rhs.w);
  }
};

const int MAX = 50000;

Car cars[MAX];
Car* carsInd[MAX];
Car carsFinal[MAX];
Car* carsFinalInd[MAX];

int main() {
    ios_base::sync_with_stdio(false);

    int testCases = 0;
    cin >> testCases;

    for(int testCase=0; testCase < testCases; ++testCase) {
        int n, w;
        int x2,y1,y2;

        cin >> n; cin >> w;
        for(int i=0; i<n; ++i) {
            cin >> cars[i].x; cin >> y1; cin >> x2; cin >> y2;
            cars[i].w=y2-y1;
            cars[i].i=i;
            cars[i].left=-1;
            cars[i].right=-1;
        }

        for(int i=0; i<n; ++i) {
            cin >> carsFinal[i].x; cin >> y1; cin >> x2; cin >> y2;
            carsFinal[i].w=y2-y1;
            carsFinal[i].i=i;
        }

        sort(cars,cars+n,compX);
        for(int i=0; i<n; ++i) {
            carsInd[cars[i].i]=&cars[i];
            cars[i].ind=i;
        }
        sort(carsFinal,carsFinal+n,compX);
        for(int i=0; i<n; ++i) {
            carsFinalInd[carsFinal[i].i]=&carsFinal[i];
            carsFinal[i].ind=i;
        }

        priority_queue<Car, vector<Car>, mycomparison> pq;

        for(int i=0; i<n; ++i) {
            while(!pq.empty() && pq.top().w+cars[i].w > w) {
                carsInd[pq.top().i]->right=cars[i].i;
                pq.pop();
            }
            pq.push(cars[i]);
        }

        while(!pq.empty()) {
        	pq.pop();
        }

        for(int i=n-1; i>=0; --i) {
            while(!pq.empty() && pq.top().w+cars[i].w > w) {
                carsInd[pq.top().i]->left=cars[i].i;
                pq.pop();
            }
            pq.push(cars[i]);
        }


        bool res=true;
        for(int i=0; i<n; ++i) {
        	int id = carsFinal[i].i;
        	if(carsInd[id]->left !=-1) {
        		if(carsFinal[i].ind<carsFinalInd[carsInd[id]->left]->ind) {
        			res=false;
        			break;
        		}
        	}

        	if(carsInd[id]->right !=-1) {
        		if(carsFinal[i].ind>carsFinalInd[carsInd[id]->right]->ind) {
        			res=false;
        			break;
        		}
        	}

        }

        if(res) {
        	cout << "TAK\n";
        } else {
        	cout << "NIE\n";
        }

    }

    return 0;
}