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

using namespace std;

#define MAX 50001
int w;
long long int nx,x1,Y1,x2,y2,H[MAX],X[MAX],DX[MAX],M[MAX],T[MAX],A[MAX];
vector<int> mess;
vector<int> orde;

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long ab(long long a) { return a > 0 ? a : -a; }

class MessComparator {
	public:
		bool operator() (const int& a, const int& b) {
			return X[a] < X[b];
		}
} mc;

class OrderComparator {
	public:
		bool operator() (const int& a, const int& b) {
			return DX[a] < DX[b];
		}
} oc;

// merge sort based on http://www.sourcetricks.com/2011/06/merge-sort.html

bool merge(int p, int r)
{
    int mid = (p + r) / 2;
    int i1 = 0;
    int i2 = p;
    int i3 = mid + 1;

    while ( i2 <= mid && i3 <= r )
        if ( DX[T[i2]] < DX[T[i3]] )
		
            A[i1++] = T[i2++];
        else {
	    if (H[T[i3]] > w - M[T[i2]]) {
		return false;
	    } 
	    M[T[i3]] = max(H[T[i3]], M[T[i2]]);
            A[i1++] = T[i3++];
	}

    while ( i2 <= mid )
        A[i1++] = T[i2++];

    while ( i3 <= r )
        A[i1++] = T[i3++];

    for ( int i = p; i <= r; i++ )
        T[i] = A[i-p];

    for (int i = r - 1; i >= p; i--) {
    	M[T[i]] = max(H[T[i]], M[T[i+1]]);
    }
   return true;
}

bool merge_sort(int p, int r)
{
    if ( p < r )
    {
        int mid = (p + r) / 2;
        return merge_sort(p, mid) && merge_sort(mid + 1, r) && merge(p, r);
    }
 return true;
}

int main() {
	int n,t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &w);
		mess.clear();
		orde.clear();
		for (int i = 0; i < n; i++) {
			scanf("%lld%lld%lld%lld", &x1, &Y1, &x2, &y2);
			X[i] = min(x1, x2);
			M[i] = H[i] = ab(Y1 - y2);
		}
		for (int i = 0; i < n; i++) {
			scanf("%lld%lld%lld%lld", &x1, &Y1, &x2, &y2);
			DX[i] = min(x1, x2);
		}
		for (int i = 0; i < n; i++) { 
			mess.push_back(i);	
			orde.push_back(i);
		}
		sort(mess.begin(), mess.end(), mc);
		for (int i = 0; i < n; i++) T[i] = mess[i];
		sort(orde.begin(), orde.end(), oc);
		bool res = merge_sort(0,n-1);	
		printf("%s\n", res ? "TAK" : "NIE");
	}
	return 0;
}