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
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<utility>
#include<tuple>
using namespace std;

#define FOR(I,A,B) for(int I=(A);I<=(B);I++)
#define REP(I,N) for(int I=0;I<(N);I++)
#define ALL(X) (X).begin(),(X).end()
#define PB push_back
#define MP make_pair
#define f first
#define s second

typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;
typedef vector<string> VS;

const int MAX = 50005;

int pos[MAX];
vector < tuple <int,int,int> > A,B;

int tree[4*MAX],M;

void update(int a, int b){
	int x=M+a-1;
	tree[x]=b;

	while(x>1){
		x/=2;
		tree[x]=max(tree[2*x],tree[2*x+1]);
	}
}

int calc(int a, int b){
	if(a>b) return 0;

	int xa=M+a-1,xb=M+b-1,res;
	res=max(tree[xa],tree[xb]);

	while(xa/2!=xb/2){
		if(xa%2==0) res=max(res,tree[xa+1]);
		if(xb%2==1) res=max(res,tree[xb-1]);
		xa/=2;
		xb/=2;
	}

	return res;
}

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

	int t;
	cin >> t;

	REP(i,t){
		A.clear();
		B.clear();
		
		int n,w;
		cin >> n >> w;

		M=1;
		while(M<n) M *= 2;

		FOR(j,1,M) tree[j] = 0;

		int x1,y1,x2,y2;

		REP(j,n){
			cin >> x1 >> y1 >> x2 >> y2;
			A.PB(make_tuple(min(x1,x2),abs(y2-y1),j));
		}

		REP(j,n){
			cin >> x1 >> y1 >> x2 >> y2;
			B.PB(make_tuple(max(x1,x2),abs(y2-y1),j));
		}

		sort(ALL(A));
			
		sort(ALL(B));
		reverse(ALL(B));

		REP(j,n){
			pos[get<2>(A[j])] = j;
			update(j+1,get<1>(A[j]));
		}

		bool ok = true;
		REP(j,n)
			if(calc(pos[get<2>(B[j])] + 2,n) > w - get<1>(B[j])){
				ok = false;
				break;
			}
			else{
				update(pos[get<2>(B[j])] + 1, 0);
			}

		ok ? cout << "TAK\n" : cout << "NIE\n";
	}

	return 0;
}