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 <algorithm>
#include <cstdio>
#include <cstdlib>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
#include <complex>
#include <sstream>
using namespace std;
 
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int,int> PII;
 
#define REP(i,n) for(int i=0;i<(n);++i)
#define SIZE(c) ((int)((c).size()))
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)
#define ALL(v) (v).begin(), (v).end()
 
#define pb push_back
#define mp make_pair
#define st first
#define nd second

int X1[100000], X2[100000], H[100000];
int P[100000];

int T[200000];
int M;
void init(int N) {
  M = 1;
  while (M < N) M <<= 1;
  REP(i,2*M) T[i] = 0;
}

void update(int v, int value) {
  v += M;
  while (v) {
    T[v] = max(T[v], value);
    v /= 2;
  }
}

int get(int A, int B, int v = 1, int L = 0, int R = M-1) {
  if (A <= L && R <= B) return T[v];
  if (R < A || B < L) return -1;
  return max(get(A,B,2*v,L,(L+R)/2), get(A,B,2*v+1,(L+R)/2+1,R));
}

void scase() {
  int N,W;
  scanf("%d%d",&N,&W);
  REP(i,N) {
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    X1[i] = min(x1,x2);
    H[i] = abs(y1-y2);
  }
  REP(i,N) {
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    X2[i] = min(x1,x2);
  }
  
  vector<PII> V1;
  REP(i,N) V1.push_back(PII(X1[i], i));
  sort(V1.begin(), V1.end());

  vector<PII> V2;
  REP(i,N) V2.push_back(PII(X2[i], i));
  sort(V2.begin(), V2.end());

  REP(i,N) P[V2[i].nd] = i;  
  
  init(N);
  REP(i,N) {
    int c = V1[i].nd;
  
    int p = P[c];
        
    int m = get(p+1,N-1);
    if (m + H[c] > W) {
      printf("NIE\n");
      return;
    }
    update(p, H[c]);
  }
  printf("TAK\n");
}

int main() {
  int T;
  scanf("%d",&T);
  REP(t,T) scase();
}