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
#include <cstdio>
#include <algorithm>
#define MAKS 50010
using namespace std;
int prawy1[MAKS];
int prawy2[MAKS];
int wys[MAKS];
inline int bw(int x){return (x>0?x:-x);}
int kol1[MAKS];
int odwrkol1[MAKS];
int kol2[MAKS];
int drz[MAKS*4];
int LD;
bool cmp1(int a, int b)
{
    if(prawy1[a]!=prawy1[b])return prawy1[a]<prawy1[b];
    return a<b;
}
bool cmp2(int a, int b)
{
    if(prawy2[a]!=prawy2[b])return prawy2[a]<prawy2[b];
    return a<b;
}

void wstaw(int v, int x)
{
    v+=LD;
    drz[v]=x;
    v/=2;
    while(v>0)
    {
        drz[v]=max(drz[2*v],drz[2*v+1]);
        v/=2;
    }
}
int maks(int l, int p)
{
	int ret=0;
	l+=LD; p+=LD;
	while(l<p)
	{
		if(l%2==0)l/=2;
		else
		{
			ret=max(ret,drz[l]);
			l++;
			l/=2;
		}
		if(p%2==1)p/=2;
		else
		{
			ret=max(ret,drz[p]);
			p--;
			p/=2;
		}
	}
	if(l==p)ret=max(ret,drz[l]);
	return ret;
}

int main()
{
    int t,n,W;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&W);
        for(int i=0;i<n;i++)
        {
            int x1,y1,x2,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            wys[i]=bw(y1-y2);
            prawy1[i]=max(x1,x2);
        }
        for(int i=0;i<n;i++)
        {
            int x1,y1,x2,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            prawy2[i]=max(x1,x2);
        }
        
        for(int i=0;i<n;i++)kol1[i]=i;
        for(int i=0;i<n;i++)kol2[i]=i;
        sort(kol1,kol1+n,cmp1);
        sort(kol2,kol2+n,cmp2);
        for(int i=0;i<n;i++)odwrkol1[kol1[i]]=i;
        
        LD=1;
        while(LD<n)LD*=2;
        for(int i=0;i<LD*2;i++)drz[i]=0;
        
        bool ok=true;
        for(int q=0;q<n;q++)
        {
            int i=kol2[q];
            int v=odwrkol1[i];
            
            // maks na przedziale <v,n>
            int m=maks(v,n-1);
            if(m>W-wys[i])
            {
                ok=false;
                break;
            }
            
            wstaw(v,wys[i]);
        }
        if(ok)puts("TAK");
        else puts("NIE");
    }
}