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
130
131
132
133
134
135
#include <iostream>
using namespace std;

int start[50000][3];
int stop[50000][3];

int tym[50000][3];
int kolej_p[50001];
int kolej_k[50001];

int partition(int tablica[50000][3], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x
{
	int x = tablica[p][1]; // obieramy x
	int i = p, j = r, w; // i, j - indeksy w tabeli
	while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j
	{
		while (tablica[j][1] > x) // dopoki elementy sa wieksze od x
			j--;
		while (tablica[i][1] < x) // dopoki elementy sa mniejsze od x
			i++;
		if (i < j) // zamieniamy miejscami gdy i < j
		{
			for(int k = 0; k < 3; k++)
			{
				w = tablica[i][k];
				tablica[i][k] = tablica[j][k];
				tablica[j][k] = w;
			}
			i++;
			j--;
		}
		else // gdy i >= j zwracamy j jako punkt podzialu tablicy
			return j;
	}
}
 
void quicksort(int tablica[50000][3], int p, int r) // sortowanie szybkie
{
	int q;
	if (p < r)
	{  
		q = partition(tablica,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu
		quicksort(tablica, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
		quicksort(tablica, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
	}
}

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

//Wczytywanie
	int t; //testy
	int a; //ilość aut na parkingu
	int p; //wysokość parkingu (szer. nieskoń.)
	
	cin>>t;
	
	for (int j=0; j<t; j++)
	{
      cin>>a;
	   cin>>p;
	
		for (int i=0; i<a; i++)
		{
			int w1[2], w2[2]; //wierzchołki
			
			cin>> w1[0];
			cin>> w1[1];
			cin>> w2[0];
			cin>> w2[1];
			int wys = w2[1]-w1[1];
			start[i][0] = i+1;		//nr auta
			start[i][1] = w1[0];	//wartość x dla ustawienia auta
			start[i][2] = wys;		//wysokość auta
      }
      
      for (int i=0; i<a; i++)
      {
         int w1[2], w2[2];
			
			cin>> w1[0];
			cin>> w1[1];
			cin>> w2[0];
			cin>> w2[1];
			int wys = w2[1]-w1[1];
			stop[i][0] = i+1;
			stop[i][1] = w1[0];
			stop[i][2] = wys;
		}

		//sortowanie po x (w1[0])
		quicksort(start, 0, a - 1);
		quicksort(stop, 0, a -1);
		
		//sortowanie startu po numerach aut
		for (int i=0; i<a; i++)
		{
			int nr = start[i][0];		//numer auta stopu znajdującego się na miejscu i
			kolej_p[nr]= i;				//dla auta o danym numerze przypisujemy jego miejsce w kolejce
		}
		
		//sortowanie stopu po numerach aut
		for (int i=0; i<a; i++)
		{
			int nr = stop[i][0];		//numer auta stopu znajdującego się na miejscu i
			kolej_k[nr]= i;				//dla auta o danym numerze przypisujemy jego miejsce w kolejce
		}
		
		//sprawdzanie
		bool spr = true;
		
		for (int i=1; i<=a; i++)
		{
			for (int j=i+1; j<=a; j++)
			{
				if (!(kolej_k[i] < kolej_k[j] && kolej_p[i] < kolej_p[j]) && !(kolej_k[i] > kolej_k[j] && kolej_p[i] > kolej_p[j]))
				{
					if (start[kolej_p[i]][2] + start[kolej_p[j]][2] > p)
					{
						spr = false;
						i=a;
						break;
					}
				}
			}
		}
			
		//wypisywanie
		if (spr)
			cout<<"TAK\n";
		else
			cout<<"NIE\n";		
	}
}