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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <stdio.h>
#define lli long long int
using namespace std;
int n;
lli w;
short int t;
lli x,y,x2,y2;

int stare[50000][4];
int nowe[50000][4];
bool odp[50000];
bool duplo=false;
lli  wtf = 0;
int main()
{
	int licznik = 0;

	scanf("%i",&t);

	for(int i = 0; i< t; i++)odp[i] = true;

		for(int i  = 0; i< t; i++)
		{
			scanf("%i",&n);
			scanf("%lli",&w);
			for(int k = 0; k< n; k++)
			{
				scanf("%lli",&x);
				stare[k][0] = x;
				scanf("%lli",&y);
				stare[k][1] = y;
				scanf("%lli",&x2);
				stare[k][2] = x2;
				scanf("%lli",&y2);
				stare[k][3] = y2;

				stare[k][0] = x;

				if(stare[k][3] - stare[k][1] >= wtf)wtf = stare[k][3] - stare[k][1];





			}

			for(int k = 0; k< n; k++)
			{
				scanf("%lli",&x);
				nowe[k][0] = x;
				scanf("%lli",&y);
				nowe[k][1] = y;
				scanf("%lli",&x2);
				nowe[k][2] = x2;
				scanf("%lli",&y2);
				nowe[k][3] = y2;
               if(nowe[k][3] - nowe[k][1] >= wtf)wtf = nowe[k][3] - nowe[k][1];

			}

			for(int k = 0; k<n; k++)
			{
				for(int j =0; j<n;j++)
				{
				if(j != k)
				{
					if(stare[j][0] < nowe[k][2] && stare[j][2] > nowe[k][0] && stare[j][1] < nowe[k][3] && stare[j][3] > nowe[k][1])
					{

						/*odp[i] = 0;
						break;*/
						for(int b = 0; b<n;b++)
                            {
                                if(b != k)
                                {

                                    if(nowe[k][0] == stare[b][0] && nowe[k][1] == stare[b][1] && nowe[k][2] == stare[b][2] && nowe[k][3] == stare[b][3])
                                    {

                                         if(stare[b-1][3] - stare[b-1][1] == w)
                                                {
                                                    duplo = false;
                                                    break;
                                                }
                                         if( stare[b][3] + wtf <= w)
                                        {


                                            duplo = true;
                                            break;
                                        }
                                        if(  (stare[b][3] + (nowe[k][3]-nowe[k][1]) <=w) )
                                        {
                                            duplo = true;
                                            break;
                                        }


                                         if(stare[b][1] - wtf >= 0 )
                                        {
                                             duplo = true;
                                            break;
                                        }


                                    }//zamiana miejsc byla ziomeczku
                                }
                            }//for b
                         if(!duplo)
                            {
                                    odp[i] = 0;
                                        break;

                            }
					}
					else if(stare[j][2] > nowe[k][0] && stare[j][0] < nowe[k][2] && stare[j][1] < nowe[k][3] && stare[j][3] > nowe[k][1] )
					{

					   for(int b = 0; b<n;b++)
                            {
                                if(b != k)
                                {

                                    if(nowe[k][0] == stare[b][0] && nowe[k][1] == stare[b][1] && nowe[k][2] == stare[b][2] && nowe[k][3] == stare[b][3])
                                    {

                                         if(stare[b-1][3] - stare[b-1][1] == w)
                                                {
                                                    duplo = false;
                                                    break;
                                                }
                                          if( stare[b][3] + wtf <= w)
                                        {


                                            duplo = true;
                                            break;
                                        }
                                        if(  (stare[b][3] + (nowe[k][3]-nowe[k][1]) <=w) )
                                        {
                                            duplo = true;
                                            break;
                                        }

                                         if(stare[b][1] - wtf >= 0 )
                                        {
                                             duplo = true;
                                            break;
                                        }


                                    }//zamiana miejsc byla ziomeczku
                                }
                            }//for b
                         if(!duplo)
                            {
                                    odp[i] = 0;
                                        break;

                            }

					}
					else if(stare[j][0] > nowe[k][0] && stare[j][0] < nowe[k][2] && stare[j][2] > nowe[k][0] && stare[j][2] < nowe[k][2] && stare[j][3] > nowe[k][1] && stare[j][3] < nowe[k][3] && stare[j][1] < nowe[k][1])
                    {

                        for(int b = 0; b<n;b++)
                            {
                                if(b != k)
                                {

                                    if(nowe[k][0] == stare[b][0] && nowe[k][1] == stare[b][1] && nowe[k][2] == stare[b][2] && nowe[k][3] == stare[b][3])
                                    {

                                         if(stare[b-1][3] - stare[b-1][1] == w)
                                                {
                                                    duplo = false;
                                                    break;
                                                }

                                         if( stare[b][3] + wtf <= w)
                                        {


                                            duplo = true;
                                            break;
                                        }
                                        if(  (stare[b][3] + (nowe[k][3]-nowe[k][1]) <=w) )
                                        {
                                            duplo = true;
                                            break;
                                        }

                                         if(stare[b][1] - wtf >= 0 )
                                        {
                                             duplo = true;
                                            break;
                                        }


                                    }//zamiana miejsc byla ziomeczku
                                }
                            }//for b
                         if(!duplo)
                            {
                                    odp[i] = 0;
                                        break;

                            }

                    }
                    else if(stare[j][0] < nowe[k][0] && stare[j][2] > nowe[k][0] && stare[j][1] > nowe[k][1] && stare[j][3] > nowe[k][1] && stare[j][3] < nowe[k][3])
                    {
                        for(int b = 0; b<n;b++)
                            {
                                if(b != k)
                                {

                                    if(nowe[k][0] == stare[b][0] && nowe[k][1] == stare[b][1] && nowe[k][2] == stare[b][2] && nowe[k][3] == stare[b][3])
                                    {

                                                if(stare[b-1][3] - stare[b-1][1] == w)
                                                {
                                                    duplo = false;
                                                    break;
                                                }


                                         if( stare[b][3] + wtf <= w)
                                        {


                                            duplo = true;
                                            break;
                                        }
                                        if(  (stare[b][3] + (nowe[k][3]-nowe[k][1]) <=w) )
                                        {
                                            duplo = true;
                                            break;
                                        }

                                         if(stare[b][1] - wtf >= 0 )
                                        {
                                             duplo = true;
                                            break;
                                        }


                                    }//zamiana miejsc byla ziomeczku
                                }
                            }//for b
                         if(!duplo)
                            {
                                    odp[i] = 0;
                                        break;

                            }
                    }



					/*else if(stare[j][0] < nowe[k][0] && stare[j][2] > nowe[k][0] && stare[j][3] > nowe[k][3] && stare[j][1] > nowe[k][1] && stare[j][1] < nowe[k][3])
					{
						cout << "Stare " << j << "koliduje z nowym " << k << endl;
					odp[i] = 0;
						break;
					}*/
				}
			}//for j
			if(duplo)
            {
                odp[i] = true;
                duplo = false;
            }
			}// for k

		}//testy


		for(int i = 0; i< t; i++)
		{
			if(odp[i]) printf("%s\n","TAK");
			else printf("%s\n","NIE");
		}
			return 0;
}