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
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 50000;

struct Sam
{
    int x, y, h, ind;
    Sam(){}
    Sam(int _x, int _y, int _h, int _ind) : x(_x), y(_y), h(_h), ind(_ind) {}
};

bool operator< (Sam a, Sam b)
{
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

Sam tab[MAX_N], plan[MAX_N];
int nr[MAX_N];


int drz[1<<20], N;

void ustaw(int p, int x)
{
    p += N;
    while(p)
    {
        drz[p] = max(drz[p], x);
        p /= 2;
    }
}

int pytaj(int p, int k)
{
    p += N;
    k += N;
    int wyn = max(drz[p], drz[k]);
    while(p/2 != k/2)
    {
        if(p%2 == 0)
            wyn = max(wyn, drz[p+1]);
        if(k%2 == 1)
            wyn = max(wyn, drz[k-1]);
        p/=2;
        k/=2;
    }
    return wyn;
}


int main()
{
    int t;
    scanf("%d", &t);

    while(t--)
 {
    int n, W;
    scanf("%d%d", &n, &W);

    int x1, y1, x2, y2;
    for(int i=0; i < n; i++)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        tab[i] = Sam(min(x1,x2), min(y1,y2), abs(y1-y2), i);
    }
    sort(tab, tab+n);
    for(int i=0; i < n; i++)
        nr[tab[i].ind] = i;

    for(int i=0; i < n; i++)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        plan[i] = Sam(min(x1,x2), min(y1,y2), abs(y1-y2), nr[i]);
    }
    sort(plan, plan+n);


    N = 1;
    while(N < n) N *= 2;
    for(int i=1; i < 2*N; i++)
        drz[i] = 0;


    bool wynik = 1;
    for(int i=0; i < n; i++)
    {
        if(plan[i].h + pytaj(plan[i].ind, n-1) > W)
            wynik = 0;
        ustaw(plan[i].ind, plan[i].h);
    }

    if(wynik)   printf("TAK\n");
    else        printf("NIE\n");
 }
}