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
#include <cstdio>

using namespace std;

const int nmax=50000;
const int tmax=20;

struct rectangle {
          unsigned long long int x1,x2,y1,y2;
          unsigned long long int height;
          unsigned long long int id;
          unsigned long long int sequence;
          unsigned long long int spare;
          };
          
struct test {
          unsigned long long int n,w;
          rectangle rectini[nmax];
          rectangle rectfin[nmax];
};

int main() {
    unsigned int t;
    unsigned long long int temp;
    test* tests = new test[tmax];
    scanf("%d",&t);
    for(int it=0; it<t; it++) {
            scanf("%u %u",&tests[it].n,&tests[it].w);
            for(int in=0; in<tests[it].n; in++) scanf("%u %u %u %u",&tests[it].rectini[in].x1,&tests[it].rectini[in].y1,&tests[it].rectini[in].x2,&tests[it].rectini[in].y2);
            for(int in=0; in<tests[it].n; in++) scanf("%u %u %u %u",&tests[it].rectfin[in].x1,&tests[it].rectfin[in].y1,&tests[it].rectfin[in].x2,&tests[it].rectfin[in].y2);
    }
    
    for(int it=0; it<t; it++) {
            for(int in=0; in<tests[it].n; in++) {
                    if ((tests[it].rectini[in].x1>=tests[it].rectini[in].x2)&&(tests[it].rectini[in].y1<=tests[it].rectini[in].y2)) {
                          temp = tests[it].rectini[in].x1;
                          tests[it].rectini[in].x1=tests[it].rectini[in].x2;
                          tests[it].rectini[in].x2=temp;                                                                                                  
                    }
                    if ((tests[it].rectini[in].x1<=tests[it].rectini[in].x2)&&(tests[it].rectini[in].y1>=tests[it].rectini[in].y2)) {
                          temp = tests[it].rectini[in].y1;
                          tests[it].rectini[in].y1=tests[it].rectini[in].y2;
                          tests[it].rectini[in].y2=temp;                                                                                                  
                    }
                    if ((tests[it].rectini[in].x1>=tests[it].rectini[in].x2)&&(tests[it].rectini[in].y1>=tests[it].rectini[in].y2)) {
                          temp = tests[it].rectini[in].x1;
                          tests[it].rectini[in].x1=tests[it].rectini[in].x2;
                          tests[it].rectini[in].x2=temp;
                          temp = tests[it].rectini[in].y1;
                          tests[it].rectini[in].y1=tests[it].rectini[in].y2;
                          tests[it].rectini[in].y2=temp;                                                                                                  
                    }
                    tests[it].rectini[in].height=tests[it].rectini[in].y2-tests[it].rectini[in].y1;
                    tests[it].rectini[in].id=in;
                    tests[it].rectini[in].sequence=0;
                    tests[it].rectini[in].spare=tests[it].w-tests[it].rectini[in].height;
                    if ((tests[it].rectfin[in].x1>=tests[it].rectfin[in].x2)&&(tests[it].rectfin[in].y1<=tests[it].rectfin[in].y2)) {
                          temp = tests[it].rectfin[in].x1;
                          tests[it].rectfin[in].x1=tests[it].rectfin[in].x2;
                          tests[it].rectfin[in].x2=temp;                                                                                                  
                    }
                    if ((tests[it].rectfin[in].x1<=tests[it].rectfin[in].x2)&&(tests[it].rectfin[in].y1>=tests[it].rectfin[in].y2)) {
                          temp = tests[it].rectfin[in].y1;
                          tests[it].rectfin[in].y1=tests[it].rectfin[in].y2;
                          tests[it].rectfin[in].y2=temp;                                                                                                  
                    }
                    if ((tests[it].rectfin[in].x1>=tests[it].rectfin[in].x2)&&(tests[it].rectfin[in].y1>=tests[it].rectfin[in].y2)) {
                          temp = tests[it].rectfin[in].x1;
                          tests[it].rectfin[in].x1=tests[it].rectfin[in].x2;
                          tests[it].rectfin[in].x2=temp;
                          temp = tests[it].rectfin[in].y1;
                          tests[it].rectfin[in].y1=tests[it].rectfin[in].y2;
                          tests[it].rectfin[in].y2=temp;                                                                                                  
                    }
                    tests[it].rectfin[in].height=tests[it].rectfin[in].y2-tests[it].rectfin[in].y1;
                    tests[it].rectfin[in].id=in;
                    tests[it].rectfin[in].sequence=0;
                    tests[it].rectfin[in].spare=tests[it].w-tests[it].rectfin[in].height;
            }
    }
    
    bool ispossible;
    for(int it=0; it<t; it++) {
            ispossible=true;
            
            unsigned long long ini,fin;
            for(int i=0; i<tests[it].n; i++) {
                    ini = tests[it].rectini[i].x1;
                    fin = tests[it].rectfin[i].x1;
                    for(int j=0; j<tests[it].n; j++) if (i!=j) {
                            if (tests[it].rectini[j].x1>=tests[it].rectini[i].x1) tests[it].rectini[j].sequence++;
                            if (tests[it].rectfin[j].x1>=tests[it].rectfin[i].x1) tests[it].rectfin[j].sequence++;
                    }
            }
            
            for(int i=0; i<tests[it].n; i++) {
                    for(int j=0; j<tests[it].n; j++) if(i!=j) {
                    if ((tests[it].rectini[i].sequence<tests[it].rectini[j].sequence) && (tests[it].rectfin[i].sequence>tests[it].rectfin[j].sequence) && (tests[it].rectfin[i].height>tests[it].rectfin[j].spare)) {
                       ispossible = false;
                       break;
                    }
                    }
                    if (!ispossible) break;
            }
            
            if(ispossible) printf("TAK\n");
            else printf("NIE\n");
    }
    
    delete [] tests;
    return 0;
}