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<stdio.h>
#include<algorithm>
#include<map>
#include<string.h>
#include<memory>
#include<iostream>
#include<cstdlib>
using namespace std;
int t[1000000]={},positions[50005];
int n,r,w;
int ile;
void add(int a,int b)
{
    a+=ile;
    t[a]=b;
    a/=2;
    while(a>=1)
    {
	t[a]=max(t[2*a],t[2*a+1]);
	a/=2;
    }
}
int find(int a,int b)
{
    if(a>b) return 0;
    a+=ile;
    b+=ile;
    int res=max(t[a],t[b]);
    while(a/2 != b/2)
    {
    
	if(a%2==0) 
	{
	    res=max(res,t[a+1]);
	}
	if(b%2==1)
	{
	    res=max(res,t[b-1]);
	}
	a>>=1;
	b>>=1;
    }
    return res;
}
struct rek
{
    int nr,x,w;
    rek(int _nr= 0, int _x = 0, int _w = 0) : nr(_nr), x(_x), w(_w){}
    bool operator<(const rek & tmp) const
    {
	return x<tmp.x || (x==tmp.x && nr<tmp.nr);
    }
}tab[50000],tab2[50000];
int main()
{
    int zes;scanf("%d",&zes);
    while(zes--)
    {
	map<int,int> minIndex;
	scanf("%d%d",&n,&w);
	for (int pot=1,i=0;;i++,pot*=2)
	    if(pot>=n) {ile=pot;break;}
	for (int i=0;i<n;i++)
	{
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		tab[i] = rek(i, x1, y2-y1);
	}
	sort(tab,tab+n);
	for (int i=0;i<n;i++)
	{
	    positions[tab[i].nr] = i;
	    add(i,tab[i].w);
	    minIndex[tab[i].x] = i;
	}
	for (int i=0;i<n;i++)
	{
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	    tab2[i] = rek(i, x1, y2-y1);
	}
	sort(tab2,tab2+n);
	bool ok = true;
	for (int i=0;i<n;i++)
	{ 
	   int nr = tab2[i].nr;
	   int nrInA = positions[nr];
	   int target = minIndex[tab[nrInA].x];
	   add(nrInA, -tab[nrInA].w);
	   int res = find(0, target);
	   if(res  + tab2[i].w >w)
	   {
	       ok= false;
	       break;
	   }
	}
	if(ok) printf("TAK\n");else printf("NIE\n");
	memset(t,1000000, 0);
	

    }
}