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

const int HALF = 65536;
const int TABSIZE = 2 * HALF + 4;

struct car {
    int id;
    int x1;
    int y1;
    int x2;
    int y2;
};

bool carsfromleft(const car & c1, const car & c2) {
    return c1.x1 < c2.x1;
}

inline void readcars(std::vector<car> & cars, const int n) {
    for (int j=0; j<n; ++j){
        cars[j].id = j;
        scanf("%d %d %d %d", &cars[j].x1, &cars[j].y1, 
                &cars[j].x2, &cars[j].y2);
    }
    std::sort(cars.begin(), cars.end(), carsfromleft);
}

inline int carheight(const car & c) {
    return c.y2 - c.y1;
}

int tab[TABSIZE];

inline void cleartab() {
    for (int i=0; i<TABSIZE; ++i) {
        tab[i] = 0;
    }
}

inline void insert(const int pos, const int val) {
    int x = pos + HALF;
    tab[x] = val;
    while (x != 1) {
        x /= 2;
        tab[x] = std::max(tab[2*x], tab[2*x+1]);
    }
}

inline int biggest(const int pos) {
    int x = pos + HALF;
    int max = tab[x];
    while (x != 1) {
        if (x % 2 == 1) {
            max = std::max(max, tab[x-1]);
        }
        x /= 2;
    }
    return max;
}

int main() {
    int t;
    scanf("%d", &t);
    for (int i=0; i<t; ++i) {
        int n, w;
        scanf("%d %d", &n, &w);
        std::vector<car> now(n), target(n);
        std::vector<int> whereis(n);
        cleartab();
        readcars(now, n);
        readcars(target, n);
        
        for (int j=0; j<n; ++j) {
            whereis[now[j].id] = j;
            insert(j, carheight(now[j]));
        }
        
        bool possible = true;
        for (int j=0; j<n; ++j) {
            int pos = whereis[target[j].id];
            if (pos > 0) {
                int highest = biggest(pos-1);
                if (highest + carheight(target[j]) > w) {
                    fprintf(stderr, "Auto %d nie przejedzie na pozycje %d\n",
                            target[j].id, j);
                    possible = false;
                    break;
                }
            }
            insert(pos, 0);
        }
        if (possible) {
            printf("TAK\n");
        } else {
            printf("NIE\n");
        }
    }
    return 0;
}