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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <stdio.h>
#include <stdlib.h>

#define N_MAX 50000

int t;
int n;
int w;

typedef struct {
        int x1, y1, x2, y2;
        int w;
        int nr;
} car;

car start[N_MAX];
car end[N_MAX];

int tested[N_MAX];

int car_cmp(const void *va, const void *vb)
{
        const car *a = (const car *) va;
        const car *b = (const car *) vb;

        return a->x1 - b->x1;
}

void print_car(car *c)
{
        printf("(%d), (%d, %d) (%d, %d) w %d\n", c->nr, c->x1, c->y1, c->x2, c->y2, c->w);
}

void print_tab(car *c)
{
        int i;

        for(i = 0; i < n; ++i) {
                print_car(&c[i]);
        }
}

int main()
{
        int i, j, tmp, k, nr, err;

        scanf("%d\n", &t);
        
        for(i = 0; i < t; ++i) {
                scanf("%d %d\n", &n, &w);
                for(j = 0; j < n; ++j) {
                        scanf("%d %d %d %d\n", &start[j].x1, &start[j].y1, &start[j].x2, &start[j].y2);
                        if (start[j].x1 > start[j].x2) {
                                tmp = start[j].x1;
                                start[j].x1 = start[j].x2;
                                start[j].x2 = tmp;
                        }
                        if (start[j].y1 > start[j].y2) {
                                tmp = start[j].y1;
                                start[j].y1 = start[j].y2;
                                start[j].y2 = tmp;
                        }
                        start[j].w = start[j].y2 - start[j].y1;
                        start[j].nr = j;
                }
                for(j = 0; j < n; ++j) {
                        scanf("%d %d %d %d\n", &end[j].x1, &end[j].y1, &end[j].x2, &end[j].y2);
                        if (end[j].x1 > end[j].x2) {
                                tmp = end[j].x1;
                                end[j].x1 = end[j].x2;
                                end[j].x2 = tmp;
                        }
                        if (end[j].y1 > end[j].y2) {
                                tmp = end[j].y1;
                                end[j].y1 = end[j].y2;
                                end[j].y2 = tmp;
                        }
                        end[j].w = end[j].y2 - end[j].y1;
                        end[j].nr = j;
                }

                qsort( &start, n, sizeof(car), car_cmp );
                qsort( &end, n, sizeof(car), car_cmp );

//                print_tab( (car *) &start );
//                print_tab( (car *) &end );
//                printf("\n");
//              

                for(j = 0; j < n; ++j) {
                        tested[j] = 0;
                }

                err = 0;
                for(j = 0; j < n; ++j) {
                        nr = end[j].nr;
                        k = 0;
                        while(1) {
                                if (start[k].nr == nr) {
                                        break;
                                }
                                k++;
                        }
                        k--;
                        while(k >= 0) {
                                if (tested[start[k].nr]) {
                                        k--;
                                        continue;
                                }
                                if (start[k].w + end[j].w > w) {
                                        err = 1;
                                        break;
                                }
                                k--;
                        }
                        if (err == 1) {
                                break;
                        }
                        tested[nr] = 1;
                }
                if (err == 1) {
                        printf("NIE\n");
                } else {
                        printf("TAK\n");
                }

        }

        return 0;
}