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
#include <iostream>
#include <cstdio>
#include <ctime>
#include <vector>
#include <algorithm>
#define LL long long
#define ff first
#define ss second
#define PB push_back
#define MP make_pair
#define DEBUG(x) cerr<<#x<<" "<<(x)<<endl;
using namespace std;
const int N = 50005;
int xp[N], xk[N], xp2[N], xk2[N], H[N], gdzie[N], poczatek[N], koniec[N], y, y2;
int n, t, X;
int czapa, drz[10*N];
bool cmp(int a, int b)
{
  return xk[a] < xk[b];
}
bool cmk(int a, int b)
{
  return xp2[a] < xp2[b];
}
void wrzuc(int poz, int w)
{
  poz += czapa;
  while(poz >= 1)
  {
    drz[poz] = max(drz[poz], w);
    poz >>= 1;
  }
}
int szukaj(int poza, int pozb)
{
  poza += czapa;
  pozb += czapa;
  int ret = max(drz[poza], drz[pozb]);
  while(poza/2 != pozb/2)
  {
    if(poza%2 == 0)ret = max(ret, drz[poza+1]);
    if(pozb%2 == 1)ret = max(ret, drz[pozb-1]);
    poza >>= 1;
    pozb >>= 1;
  }
  return ret;
}
void wyrzuc(int poz)
{
  poz += czapa;
  drz[poz] = 0;
  poz >>= 1;
  while(poz >= 1)
  {
    drz[poz] = max(drz[poz*2], drz[poz*2+1]);
    poz >>= 1;
  }
}
bool rozwiaz()
{
  czapa = 1;
  while(czapa <= n)czapa *= 2;
  for(int i=1; i<=n; i++)
  {
    gdzie[poczatek[i]] = i;
    wrzuc(i, H[poczatek[i]]);
  }
  for(int i=1; i<=n; i++)
  {
    int w = koniec[i];
    wyrzuc(gdzie[w]);
    if(szukaj(1, gdzie[w]) + H[w] > X)
    {
      for(int i=1; i<2*czapa; i++)drz[i] = 0;  
      return 0;
    }
  }
  for(int i=1; i<2*czapa; i++)drz[i] = 0;
  return 1;
}

int main()
{
  scanf("%d", &t);
  while(t--)
  {   
    scanf("%d%d", &n, &X);
    for(int i=1; i<=n; i++)
    {
      scanf("%d%d%d%d", &xp[i], &y, &xk[i], &y2);
      H[i] = abs(y - y2);
      if(xp[i] > xk[i])swap(xp[i], xk[i]);
    }
    for(int i=1; i<=n; i++)
    {
      scanf("%d%d%d%d", &xp2[i], &y, &xk2[i], &y2);
      if(xp2[i] > xk2[i])swap(xp2[i], xk2[i]);
    }
    for(int i=1; i<=n; i++)    
      poczatek[i] = koniec[i] = i;
    sort(poczatek+1, poczatek+1+n, cmp);
    sort(koniec+1, koniec+1+n, cmk);  
    printf(rozwiaz()? "TAK\n": "NIE\n");
  }
  return 0;
}