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
#include<stdio.h>
#include<vector>
#include<climits>
#include<algorithm>

using namespace std;

const int M=1 << 16; // rozmiar drzewa
const int N=50001;

struct bar {
    int xcord, height, index;

    bar() : xcord(0), height(0), index(0) {}
    bar(int x, int y, int z) : xcord(x), height(y), index(z) {}
};

bool operator <(const bar& a, const bar& b) {
    return a.xcord < b.xcord;
}

int Tree[2*M];

void init() {
    for(int i=0; i<2*M; ++i) Tree[i]=-1;
}

void insert(int i, int key) {
    i+=M;
    Tree[i]=key;
    while((i/=2)>0)
        Tree[i]=max(key,Tree[i]);
}

int removeMax(int i) {
   // liscie w drzewie maja indeksy od 1 w gore!
    int j=i+M-1; int maxx=Tree[j];
    while(j>1) {
        if(j%2==1) maxx=max(maxx,Tree[j-1]);
        j=j/2;
    }

    i+=M;  Tree[i]=-1;
    while((i/=2)>0) Tree[i]=max(Tree[2*i],Tree[2*i+1]);
    return maxx;
}

void order(int &x1, int &y1, int &x2, int &y2) {
    pair< int,int > coords[4];
    coords[0].first = x1; coords[0].second=y1;
    coords[1].first = x2; coords[1].second=y2;
    coords[2].first = x1; coords[2].second=y2;
    coords[3].first = x2; coords[3].second=y1;
    sort(coords,coords+4);
    x1=coords[0].first; y1=coords[0].second;
    x2=coords[3].first; y2=coords[3].second;
}

int main() {

    int t;
    scanf("%d",&t);
    bar startowy[N]; //fill(startowy,startowy+N,bar(0,0,0));
    bar docelowy[N]; //fill(docelowy,docelowy+N,bar(0,0,0));
    int T[N];

    for(int i=0; i<t; ++i) {
        int n,w,x1,x2,y1,y2;
        scanf("%d%d",&n,&w);
        for(int j=0; j<n; ++j) {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            order(x1,y1,x2,y2);
            startowy[j]=bar(x1,y2-y1,j);
        }
        for(int j=0; j<n; ++j) {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            order(x1,y1,x2,y2);
            docelowy[j]=bar(x1,y2-y1,j);
        }
        sort(startowy,startowy+n);
        sort(docelowy,docelowy+n);

        init();
        for(int j=0; j<n; ++j) {
            T[startowy[j].index]=j+1;
            insert(j+1,startowy[j].height);
        }

        bool dasie=true;
        for(int j=0; j<n; ++j) {
            int key=removeMax(T[docelowy[j].index]);
            if( w-key < docelowy[j].height ) {
                dasie=false; break;
            }
        }

        if(dasie) printf("TAK\n");
        else printf("NIE\n");
    }
return 0;
}