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
#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long int

int main()
{
	int T;
	cin >> T;
	int* pocz = new int[3*T];
	int* kon = new int[3*T];
	vector<pair<int,int> > pWs;
	vector<pair<int,int> > kWs;
	for( int t = 0; t < T; ++t )
	{
		int N, W;
		cin >> N >> W;
		bool yes = true;
		bool* vis = new bool[N];
		for( int k = 0; k < N; ++k )
			vis[k] = false;
		for( int n = 0; n < N; ++n )
		{
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			pocz[3*n] = a;
			pocz[3*n+1] = c;
			pocz[3*n+2] = d-b;
			pWs.push_back(make_pair(a,n));
		}
		for( int n = 0; n < N; ++n )
		{
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			kon[3*n] = a;
			kon[3*n+1] = c;
			kon[3*n+2] = d-b;
			kWs.push_back(make_pair(a,n));
		}
		sort(pWs.begin(),pWs.end());
		sort(kWs.begin(),kWs.end());

		for( int i = 0; i < (int)pWs.size(); ++i )
		{
			int x = pWs[i].second;
			int x1 = pocz[3*x];
			int x2 = pocz[3*x+1];
			int hx = pocz[3*x+2];
			bool past = false;
			vis[x] = true;
			for( int j = 0; j < (int)kWs.size(); ++j )
			{
				if( kWs[j].second == x )	// found our element, ignore it
				{
					past = true;
					continue;
				}
				int y = kWs[j].second;
				int y1 = kon[3*y];
				int y2 = kon[3*y+1];
				int hy = kon[3*y+2];
				if( hx + hy > W )	// height too big
				{
					if( (!(vis[y]) && !past) || (past && (x2 > y1)) ) // reverse order, or overlap
					{
						yes = false;
					}
				}
			}
			if( !yes )
				break;
		}
		if( yes )
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	return 0;
}