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
#include <stdlib.h>    
#include <iostream>
#include <map>

using namespace std;
 
long long int n, w;

struct Point{
    long long int x1,y1,x2,y2;
    long long int w;
	int id;
	bool onPlace;
};
 
Point* srcPoints[50000];
Point* dstPoints[50000];
map<int, int> id2SrcIndex;
map<int, int> id2DstIndex;

void createMap(map<int, int>& id2Index, Point** points){
	for (int ni=0;ni<n;ni++){
		pair<int, int> p(points[ni]->id, ni);
		id2Index.insert(p);
	}
}

int compare1 (const void* e1, const void* e2)
{
	Point* p1= *((Point**)e1);
	Point* p2= *((Point**)e2);
	return p1->x1-p2->x1;
}

int main(int argc, char* argv[])
{
	int t;
    cin >> t;
    for (int ti=0;ti<t;ti++){
        cin >> n >> w;
        for (int ni=0;ni<n;ni++){
			srcPoints[ni] = new Point();
            cin>>srcPoints[ni]->x1>>srcPoints[ni]->y1>>srcPoints[ni]->x2>>srcPoints[ni]->y2;
            srcPoints[ni]->w=srcPoints[ni]->y2-srcPoints[ni]->y1;
			srcPoints[ni]->id=ni;
        }
        for (int ni=0;ni<n;ni++){
			dstPoints[ni] = new Point();
            cin>>dstPoints[ni]->x1>>dstPoints[ni]->y1>>dstPoints[ni]->x2>>dstPoints[ni]->y2;
            dstPoints[ni]->w=srcPoints[ni]->w;
			dstPoints[ni]->id=ni;
        }

		qsort(srcPoints, n, sizeof(Point*), compare1);
		qsort(dstPoints, n, sizeof(Point*), compare1);

		createMap(id2SrcIndex, srcPoints);
		createMap(id2DstIndex, dstPoints);

        bool retValue=true;
 /*
		long long maxSoFar[50000];
		for (int i=0;i<50000;i++)
			maxSoFar[i]=w;
			*/
        for (int dstIndex=0;dstIndex<n;dstIndex++){
			
			Point* dstPoint = dstPoints[dstIndex];
			
			int srcIndex=id2SrcIndex[dstPoint->id];
			Point* srcPoint = srcPoints[srcIndex];

			//if (srcIndex>0 && srcPoint->w + maxSoFar[srcIndex-1] > w){
			for (int i=srcIndex-1;i>=0;i--){
				//maxSoFar[0]=0;
				for (int i=0;i<srcIndex;i++){					
					Point* tmpSrcPoint = srcPoints[i];			
					//maxSoFar[i]=maxSoFar[i-1];
					if(tmpSrcPoint->onPlace)
						continue;
					//maxSoFar[i]=max(maxSoFar[i-1], tmpSrcPoint->w);
					if (srcPoint->w+ tmpSrcPoint->w>w){
						retValue=false;
						break;
					}
				}
			}
			//else if (srcIndex>0)
			//	cout<<"A";
			srcPoint->onPlace=true;
			if (!retValue)
				break;
        }
 
		cout<<(retValue?"TAK":"NIE")<<endl;

		for (int ni=0;ni<n;ni++){
			delete srcPoints[ni];
			delete dstPoints[ni];
		}
    }
    return 0;
}