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

using namespace std;

typedef pair<int, int> pii;
typedef pair<int, pii> pa;

const int czapa=65536;
const int rozmiar=2*czapa;

struct tree{
	int T[rozmiar];
	
	void dodaj(int i, int wysokosc){
		i+=czapa;
		T[i]=max(T[i], wysokosc);
		
		while(i>1){
			i/=2;
			T[i]=max(T[2*i], T[2*i+1]);
		}
		
	}
	
	int maks(int i, int pp, int pk, int p, int k){
		if(p==pp && k==pk)
			return T[i];
			
		int result=0;
		
		int m=(pp+pk)/2;
		
		if(p<m){
			result=max(result, maks(2*i, pp, m, p, min(m, k) ) );
		}
		
		if(k>m){
			result=max(result, maks(2*i+1, m, pk, max(m, p), k) );
		}
		
		return result;
	}
};

tree pred;
vector<pa> pocz;
vector<pa> kon;
int pozycje[50001];

void clear(){
	memset(pred.T, 0, sizeof(pred.T) );
	memset(pozycje, 0, sizeof(pozycje) );
	pocz.clear();
	kon.clear();
}

bool test(int sufit){
	for(int i=0; i<pocz.size(); i++){
		int wys=pocz[i].second.first;
		int num=pocz[i].second.second;
		
		int szczelina=pred.maks(1, 0, czapa, pozycje[num], czapa);
		
		if(wys+szczelina>sufit)
			return false;
		
		pred.dodaj(pozycje[num], wys);
	}
	
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	
	int testy;
	cin>>testy;
	
	while(testy--){
		clear();
		
		int n, w;
		cin>>n>>w;
		
		for(int i=1; i<=n; i++){
			int x1, y1, x2, y2;
			cin>>x1>>y1>>x2>>y2;
			
			pocz.push_back(pa(x1, pii(abs(y2-y1), i) ) );
		}
		
		for(int i=1; i<=n; i++){
			int x1, y1, x2, y2;
			cin>>x1>>y1>>x2>>y2;
			
			kon.push_back(pa(x1, pii(abs(y2-y1), i) ) );
		}
		
		sort(pocz.begin(), pocz.end() );
		sort(kon.begin(), kon.end() );
		
		for(int i=0; i<kon.size(); i++){
			pozycje[kon[i].second.second]=i;	
		}
		
		if(test(w))
			cout<<"TAK\n";
		else
			cout<<"NIE\n";
		
		
	}
	return 0;
}