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
128
129
// Krzysztof Piesiewicz
// Parking [B] PA 2014
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 50007, MAX_SIZE = (1 << 18) + 7, DB = 0;

class Car {
public:
	int id, x, w, tx;
};

class Pos {
public:
	int x, id;
	bool st;
};

inline bool operator<( Car a, Car b ) {
	return a.x < b.x;
}

inline bool operator<( Pos a, Pos b ) {
	return a.x < b.x;
}

int t, n, w, x[ 2 ], y[ 2 ], size, tr[ 2 ][ MAX_SIZE ];
bool isPos;
Car c[ MAX_N ];
Pos p[ 2 * MAX_N ];

void updateMax( int *tree, int i, int w ) {
	i += size;
	while( i > 0 ) {
		tree[ i ] = max( tree[ i ], w );
		i >>= 1;
	}
}

int getMax( int *tree, int i, int j ) {
	i += size;
	j += size;
	int res = max( tree[ i ], tree[ j ] );
	while( i / 2 != j / 2 ) {
		if( i % 2 == 0 )
			res = max( res, tree[ i + 1 ] );
		if( j % 2 == 1 )
			res = max( res, tree[ j - 1 ] );
		i >>= 1;
		j >>= 1;
	}
	return res;
}

void print( int *tree ) {
	if( DB ) {
		for( int i = 0; i < 2 * size; i++ )
			printf( "tr %d, w %d\n", i, tree[ i ] );
		printf( "\n" );
	}
}

int main() {
	scanf( "%d", &t );
	for( ; t > 0; t-- ) {
		scanf( "%d %d", &n, &w );
		for( int i = 0; i < n; i++ ) {
			for( int j = 0; j < 2; j++ )
				scanf( "%d %d", &x[ j ], &y[ j ] );
			p[ i ].x = c[ i ].x = min( x[ 0 ], x[ 1 ] );
			c[ i ].w = abs( y[ 0 ] - y[ 1 ] );
			p[ n + i ].id = p[ i ].id = c[ i ].id = i;
			p[ i ].st = true;
		}
		for( int i = 0; i < n; i++ ) {
			for( int j = 0; j < 2; j++ )
				scanf( "%d %d", &x[ j ], &y[ j ] );
			p[ n + i ].x = c[ i ].tx = min( x[ 0 ], x[ 1 ] );
			p[ n + i ].st = false;
		}
		sort( p, p + 2 * n );
		
		for( int i = 0; i < 2 * n; i++ )
			if( p[ i ].st )
				c[ p[ i ].id ].x = i;
			else
				c[ p[ i ].id ].tx = i;
		sort( c, c + n );

		size = 1;
		while( size < 2 * n )
			size *= 2;
		for( int j = 0; j < 2; j++ )
			for( int i = 0; i < 2 * size; i++ )
				tr[ j ][ i ] = 0;
		isPos = true;
		
		for( int i = 0; i < n; i++ ) {
			if( c[ i ].x > c[ i ].tx ) {
				if( DB ) printf( "id %d, x %d, tx %d, w %d, max %d\n", c[ i ].id, c[ i ].x, c[ i ].tx, c[ i ].w, getMax( tr[ 0 ], c[ i ].tx, c[ i ].x ) );
				if( c[ i ].w + getMax( tr[ 0 ], c[ i ].tx, c[ i ].x ) > w )
					isPos = false;
				updateMax( tr[ 0 ], c[ i ].tx, c[ i ].w );
				updateMax( tr[ 1 ], c[ i ].tx, c[ i ].w );
			}
			else
				updateMax( tr[ 0 ], c[ i ].x, c[ i ].w );
		}
		print( tr[ 0 ] );print( tr[ 1 ] );
		for( int i = n - 1; i >= 0; i-- ) {
			if( c[ i ].x < c[ i ].tx ) {
				if( DB ) printf( "id %d, x %d, tx %d, w %d, max %d\n", c[ i ].id, c[ i ].x, c[ i ].tx, c[ i ].w, getMax( tr[ 1 ], c[ i ].x, c[ i ].tx ) );
				if( c[ i ].w + getMax( tr[ 1 ], c[ i ].x, c[ i ].tx ) > w )
					isPos = false;
			updateMax( tr[ 1 ], c[ i ].tx, c[ i ].w );
			}
		}
		print( tr[ 1 ] );
		if( DB )
			for( int i = 0; i < n; i++ )
				printf( "id %d, x %d, tx %d, w %d\n", c[ i ].id, c[ i ].x, c[ i ].tx, c[ i ].w );
		if( isPos )
			printf( "TAK\n" );
		else
			printf( "NIE\n" );
	}
	return 0;
}