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
// testowane tylko na tescie przykladowym ;-)
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>

using namespace std;

struct Car
{
    int height,right,id;
};
bool cmp_right(const Car& a, const Car& b)
{
    return a.right<b.right;
}

void solve_set()
{
    int n,w;
    scanf(" %d %d", &n, &w);
    vector<Car> start,target;
    start.reserve(n);
    target.reserve(n);
    for(int i=0; i<n; ++i)
    {
        int x1,y1,x2,y2;
        scanf(" %d %d %d %d", &x1, &y1, &x2, &y2);
        Car car;
        car.right = max(x1,x2);
        car.height = abs(y1-y2);
        car.id = i;
        start.push_back(car);
    }
    for(int i=0; i<n; ++i)
    {
        int x1,y1,x2,y2;
        scanf(" %d %d %d %d", &x1, &y1, &x2, &y2);
        Car car;
        car.right = max(x1,x2);
        car.height = abs(y1-y2);
        car.id = i;
        target.push_back(car);
    }
    sort(start.begin(),start.end(),cmp_right);
    sort(target.begin(),target.end(),cmp_right);

    vector<int> pos_by_id;
    pos_by_id.resize(n);
    for(unsigned int i=0;i<start.size();++i)
    {
        pos_by_id[start[i].id] = i;
    }
    int group_size = sqrt(n);
    if(group_size<2)
        group_size=2;
    int group_count = n/group_size;
    if(n%group_size)
        group_count++;
    vector<int> group_maximums(group_count,0);
    for(int i=0; i<n; ++i)
        group_maximums[i/group_size] = max(group_maximums[i/group_size],start[i].height);


    for(unsigned int i=0;i<target.size();++i)
    {
        int pos = pos_by_id[target[i].id];

        int maximum=0;
        int full_groups = pos/group_size;
        for(int g=0; g<full_groups; ++g)
            maximum = max(maximum,group_maximums[g]);
        for(int j=full_groups*group_size; j<pos; ++j)
            maximum = max(maximum,start[j].height);

        if(w-maximum>=start[pos].height)
        {
            start[pos].height = 0;

            int group_id = pos/group_size;
            int start_at = group_id*group_size;
            int end_at = min(start_at+group_size,n);
            group_maximums[group_id] = 0;
            for(int j=start_at; j<end_at; ++j)
                group_maximums[group_id] = max(group_maximums[group_id],start[j].height);

            break;
        }
        else
        {
            printf("NIE\n");
            return;
        }

    }
    printf("TAK\n");
}

int main()
{
    int t;
    scanf(" %d", &t);
    for(int i=0; i<t; ++i)
        solve_set();
    return 0;
}