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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

struct iTree {
    vector <int> tab;

    iTree () {
        tab.resize(1<<17, 0);
    }

    void repair (int x){
        while (x >= 1){
            x = x>>1;
            tab[x] = max (tab[x*2], tab[x*2+1]);
        }
    }

    void add (int x, int a){
        tab[x+(1<<16)] = max (tab[x+(1<<16)], a);
        repair (x+(1<<16));
    }

    int maxi (int a, int b, int s, int e, int v){
        if (a == s && b == e) return tab[v];
        int c = (s+e)>>1;

        if (a >= c) return maxi (a, b, c, e, v*2+1);
        else if (b < c) return maxi (a, b, s, c, v*2);
        else return max (maxi(a, c, s, c, v*2), maxi(c, b, c, e, v*2+1));
    }
};

vector <pair <int, int> > read_starting_poztions (int number_of_cars, vector <int> &cars_height){
    vector <pair <int, int> > starting_pozitions (number_of_cars, make_pair(0,0));
    cars_height.resize(number_of_cars, 0);

    for (int i=0; i<number_of_cars; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cars_height[i] = abs (y1 - y2);
        starting_pozitions[i] = make_pair(min(x1, x2), i);
    }

    sort (starting_pozitions.begin(), starting_pozitions.end());

    return starting_pozitions;
}

vector <pair <int, int> > read_ending_poztions (int number_of_cars){
    vector <pair <int, int> > ending_pozitions(number_of_cars, make_pair(0,0));

    for (int i=0; i<number_of_cars; i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ending_pozitions[i] = make_pair(max(x1, x2), i);
    }

    sort (ending_pozitions.begin(), ending_pozitions.end());

    return ending_pozitions;
}

vector <int> make_place (int number_of_cars, vector <pair <int, int> > ending_pozitions){
    vector <int> place (number_of_cars, 0);

    for (int i=0; i<number_of_cars; i++)
        place[ending_pozitions[i].second] = i;

    return place;
}

bool tryit (int number_of_cars, vector <pair <int, int> > starting_pozitions, vector <int> place, vector <int> cars_height, int parking_height){
    int car;
    iTree T;

    for (int i=0; i<number_of_cars; i++) {
        car = starting_pozitions[i].second;
        if (T.maxi(place[car]+(1<<16), 1<<17, 1<<16, 1<<17, 1) + cars_height[car] <= parking_height)
            T.add(place[car], cars_height[car]);
        else return false;
    }
    return true;
}

void solve (){
    int number_of_cars, parking_height; cin >> number_of_cars >> parking_height;
    vector <pair <int, int> > starting_pozitions, ending_pozitions;
    vector <int> cars_height, place;

    starting_pozitions = read_starting_poztions(number_of_cars, cars_height);
    ending_pozitions = read_ending_poztions(number_of_cars);
    place = make_place(number_of_cars, ending_pozitions);

    if (tryit(number_of_cars, starting_pozitions, place, cars_height, parking_height))
        cout << "TAK\n";
    else cout << "NIE\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    int t; cin >> t;
    for (int i=0; i<t; i++) solve();
    return 0;
}