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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// Author: Adam Krasuski

#include <cstdio>
#include <algorithm>

using namespace std;

struct car{
    int number;
    int width;
    int position;
};

car initial_situation[50009];
car final_situation[50009];
int final_pos[50009];
car temporary[50009];

int abs(int a){
    if(a<0){return -a;}
    return a;
}

int cmp_pos(car a,car b){
    return a.position<b.position;
}

int cmp_final_pos(int a,int b){
    return final_pos[a]<final_pos[b];
}

int is_correct_merge_sort(int left,int right,int width){// <left,right)
    //sorts initial_situation according to final pos
    if(left>=right-1){
        return 1;//correct, and sorted
    }
    int middle=(right+left)/2;
    int a=is_correct_merge_sort(left,middle,width);
    int b=is_correct_merge_sort(middle,right,width);
    if(a&&b){
        //both correct
        //now merging left and right halves into temporary array, while checking if all switches are possible
        int i=left;//index of left array
        int j=middle;//index of right array
        int k=0;//index of temporary array

        int max_left=2e9;
        while(k<right-left){
            int p;
            if(i>=middle){
                //push j-th
                p=1;
            }
            else if(j>=right){
                //push i-th
                p=0;
            }
            else if(cmp_final_pos(initial_situation[i].number,initial_situation[j].number)){
                //push i-th
                p=0;
            }
            else{
                //push j-th
                p=1;
            }
            if(p){
                temporary[k]=initial_situation[j];
                j++;
                if(width-temporary[k].width<max_left){
                    max_left=width-temporary[k].width;
                }
            }
            else{
                temporary[k]=initial_situation[i];
                i++;
                if(temporary[k].width>max_left){
                    return 0;//invalid!
                }
            }
            k++;
        }
        for(int i=0;i<k;i++){
            initial_situation[i+left]=temporary[i];
        }
        return 1;//ok!
    }
    else{
        return 0;
    }
}

int main(){
    int t;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
        int n,w;
        scanf("%d %d",&n,&w);
        for(int j=0;j<n;j++){
            int x1,x2,y1,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            car c1={j,abs(y2-y1),min(x1,x2)};
            initial_situation[j]=c1;
        }
        for(int j=0;j<n;j++){
            int x1,x2,y1,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            car c1={j,abs(y2-y1),min(x1,x2)};
            final_situation[j]=c1;
        }
        sort(initial_situation,initial_situation+n,cmp_pos);
        sort(final_situation,final_situation+n,cmp_pos);
        for(int j=0;j<n;j++){
            final_pos[final_situation[j].number]=j;
        }

        /*
        printf("Initially:\n");
        for(int j=0;j<n;j++){
            printf("Next car is at position %d, with number %d\n",initial_situation[j].position,initial_situation[j].number);
        }
        printf("Finally:\n");
        for(int j=0;j<n;j++){
            printf("Next car is at position %d, with number %d\n",final_situation[j].position,final_situation[j].number);
        }
        for(int j=0;j<n;j++){
            printf("Final position of car number %d is %d\n",j,final_pos[j]);
        }
        */

        int result=is_correct_merge_sort(0,n,w);

        /*
        printf("After sorting, the cars are at:\n");
        for(int j=0;j<n;j++){
            printf("Next car is at position %d, with number %d\n",initial_situation[j].position,initial_situation[j].number);
        }
        printf("Result (0/1): %d\n",result);
        */

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


}