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
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct _auto{
  int id;
  int start;
  int dim;
  int finish;
};

bool sort_start(const _auto &a, const _auto &b){
  return a.start < b.start;
}

bool merge(_auto*,_auto*,int,int,int,int);

bool mergesort(_auto *a, _auto*b, int low, int high,int w)
{
    int pivot;
    if(low<high)
    {
        pivot=(low+high)/2;
        bool w1 = mergesort(a,b,low,pivot,w);
        if(!w1) return w1;
        w1 = mergesort(a,b,pivot+1,high,w);
        if(!w1) return w1;
        w1 = merge(a,b,low,pivot,high,w);
        if(!w1) return w1;
    }
    return true;
}

bool merge(_auto *a, _auto *b, int low, int pivot, int high,int w)
{
    int h,i,j,k;
    h=low;
    i=low;
    j=pivot+1;
    while((h<=pivot)&&(j<=high))
    {   
        
        if(a[h].finish<=a[j].finish)
        {
            if(w-a[h].dim<a[j].dim)
              return false;
            b[i]=a[h];
            h++;
        }
        else
        {
            b[i]=a[j];
            j++;
        }
        i++;
    }
    if(h>pivot)
    {
        for(k=j; k<=high; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    else
    {
        for(k=h; k<=pivot; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    for(k=low; k<=high; k++) a[k]=b[k];
    return true;
}


int main(){
  int d, dd;
  scanf("%d",&d);
  while(d--){
    int n,w,aa;
    int x,xx,y,yy;
    scanf("%d%d",&n,&w);
    _auto auta[n];
    _auto auta2[n];
    for(int i=0;i<n;i++){     
      scanf("%d%d%d%d",&x,&y,&xx,&yy);
      aa = min(abs(x-xx),abs(y-yy));
      _auto a={i,min(x,xx),aa,0};
      auta[i]=a;
    }
    
    for(int i=0;i<n;i++){     
      scanf("%d%d%d%d",&x,&y,&xx,&yy);
      auta[i].finish = min(x,xx);
    } 
    sort(auta,auta+n,sort_start);
    bool i=mergesort(auta, auta2, 0, n-1,w);
    printf("%s\n",!i?"TAK":"NIE");



 }
}