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
//
//  main.cpp
//  PA_2014_PAR
//
//  Created by Michal Kowalski on 14/05/14.
//  Copyright (c) 2014 Michal Kowalski. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>

using namespace std;

int t;
int n,w;

//int X1[50009];
//int X2[50009];
//int Y1[50009];
//int Y2[50009];
//
//int kX1[50009];
//int kX2[50009];
//int kY1[50009];
//int kY2[50009];

int POS1[50009];
int POS2[50009];

int MIN_D[50009];
vector<pair<pair<int,int>, int> > oP;
vector<pair<pair<int,int>, int> > oK;

void do_the_magic();
int main()
{
    scanf("%d",&t);
    for(int x=0;x<t;++x)
    {
        scanf("%d %d",&n,&w);
        oP.clear();
        oK.clear();
        for (int y=1; y<=n; ++y) {
            int x1,x2,y1,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            int minX = min(x1,x2);
            int maxX = max(x1,x2);
            int minY = min(y1,y2);
            int maxY = max(y1,y2);
            oP.push_back(pair<pair<int,int>, int>(pair<int,int>(minX,maxX),y));
            MIN_D[y] = maxY-minY;
        }
        
        for (int y=1; y<=n; ++y) {
            int x1,x2,y1,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            int minX = min(x1,x2);
            int maxX = max(x1,x2);
            oK.push_back(pair<pair<int,int>, int>(pair<int,int>(minX,maxX),y));
        }
        
        do_the_magic();
        
    }
    
    return 0;
}

void do_the_magic()
{
    sort(oP.begin(), oP.end(), less<pair<pair<int,int>, int> >());
    sort(oK.begin(), oK.end(), less<pair<pair<int,int>, int> >());
    
    for(int x=0;x<oK.size();++x)
        POS2[oK[x].second] = x;
    
    unsigned long opsize = oP.size();
    for (int i=0; i<opsize-1; ++i) {
        for(int j=i+1;j<opsize;++j)
        {
            int i_id = oP[i].second;
            int j_id = oP[j].second;
            if (POS2[i_id] > POS2[j_id])
            {
                if (MIN_D[i_id]+MIN_D[j_id]> w)
                {
                    printf("NIE\n");
                    return;
                }
            }
                
        }
    }
    
    printf("TAK\n");
}