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

using namespace std;

int n, wysokosc;

struct S
{
  int nr, x, wys;
  
  bool operator<(const S &p) const
  {
    return x<p.x;
  }
} przed[50000], po[50000];
int gdziePrzed[50000];


int drzewo[200000], lisc;

void budujDrzewo()
{
  memset(drzewo, 0, sizeof(drzewo));
  lisc=1;
  while (lisc<n)
    lisc*=2;
  for (int i=0; i<n; ++i)
    drzewo[lisc+i]=przed[i].wys;
  for (int i=lisc-1; i>0; --i)
    drzewo[i]=max(drzewo[2*i], drzewo[2*i+1]);
}

int maks(int poz)
{
  int wyn=0;
  poz+=lisc;
  while (poz>1)
  {
    int r=poz/2;
    if (poz==r*2+1)
      wyn=max(wyn, drzewo[r*2]);    
    poz=r;
  }  
  return wyn;
}

void zeruj(int poz)
{
  poz+=lisc;
  drzewo[poz]=0;
  while (poz>1)
  {
    poz/=2;
    drzewo[poz]=max(drzewo[2*poz], drzewo[2*poz+1]);
  }  
}

bool przejedzie(int nr)
{
  int pozPrzed=gdziePrzed[nr];
  if (wysokosc<przed[pozPrzed].wys+maks(pozPrzed))
    return false;
  zeruj(pozPrzed);
  return true;
}

bool przejedzieX(int nr)
{
  int wys=przed[gdziePrzed[nr]].wys;
  for (int i=gdziePrzed[nr]-1; i>=0; --i)
    if (wys+przed[i].wys>wysokosc)
      return false;  
  przed[gdziePrzed[nr]].wys=0;
  return true;
}

bool daSie()
{
  cin>>n>>wysokosc;
  for (int i=0; i<n; ++i)
  {
    int x1, x2, y1, y2;
    cin>>x1>>y1>>x2>>y2;
    przed[i].nr=i;
    przed[i].x=min(x1, x2);
    przed[i].wys=abs(y1-y2);
  }
  sort(przed, przed+n);
  for (int i=0; i<n; ++i)
  {
    gdziePrzed[przed[i].nr]=i;
    int x1, x2, y1, y2;
    cin>>x1>>y1>>x2>>y2;
    po[i].nr=i;
    po[i].x=min(x1, x2);
    po[i].wys=abs(y1-y2);
  }
  sort(po, po+n);
  budujDrzewo();
  for (int i=0; i<n; ++i)
    if (!przejedzie(po[i].nr))
      return false;  
  return true;
}

int main()
{
  ios_base::sync_with_stdio(false);
  int t;
  cin>>t;
  for (int tt=0; tt<t; ++tt)
    cout<<(daSie() ? "TAK" : "NIE")<<endl;
  return 0;
}