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
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define SORT(X) sort(X.begin(),X.end())
#define fi first
#define se second

struct Tree{
  const static int N = 1024*512;
  int D[1024*1024];
  
  void clear(){
    FOR(i,N*2) D[i] = 0;
  }
  
  void dod(int a, int b){
    a += N;
    while(a){
      D[a] = max(D[a],b);
      a /= 2;
    }
  }
  
  int maks(int a){
    a += N;
    int b = N*2-7;
    int ans = 0;
    while(a+1 < b){
      ans = max(ans,D[a]);
      ans = max(ans,D[b]);
      b = (b-1)/2;
      a = (a+1)/2;
    }
    if(a == b) ans = max(ans,D[b]);
    return ans;
  }
  
}X;

int G[1000100];
vector<pair<int,int> > Ev;
int W[1000100];
vector<pair<int,int> > Tr;

void test(){
  while(!Ev.empty()) Ev.pop_back();
  while(!Tr.empty()) Tr.pop_back();
  X.clear();
  
  int n,w;
  scanf("%d%d",&n,&w);
  FOR(i,n){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    W[i] = abs(b-d);
    Ev.pb(mp(min(a,c),i));
  }
  FOR(i,n){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    W[i] = abs(b-d);
    Tr.pb(mp(min(a,c),i));
  }
  sort(Tr.begin(),Tr.end());
  FOR(i,SZ(Tr)) G[Tr[i].se] = i;
  sort(Ev.begin(),Ev.end());
  FOR(q,SZ(Ev)){
    int i = Ev[q].se;
    int tar = G[i];
    if(X.maks(tar) + W[i] > w){
      printf("NIE\n");
      return;
    }
    X.dod(tar,W[i]);
  }
  
  printf("TAK\n");
}

int main () {
  int t;
  scanf("%d",&t);
  while(t--) test();
}