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
112
113
114
115
116
#include <iostream>
#include <cmath>
using namespace std;

struct car
{
    int nr,x1,h;
};

car poczatkowo[50001];
car koncowo[50001];
int szczeliny[50001];
int gdzie_jest[50001];
bool nbufor[50001];

void sortowanie(int N,car* t)
{
    car tmp;
    int i,j,k,m,x;
     for(i = 2; i <= N; i++)
  {
    j = i; k = j / 2;
    tmp=t[i];
    x=t[i].x1;
    while((k > 0) && (t[k].x1 < x))
    {
      t[j] = t[k];
      j = k; k = j / 2;
    }
    t[j] = tmp;
  }

  for(i = N; i > 1; i--)
  {
    swap(t[1], t[i]);
    j = 1; k = 2;
    while(k < i)
    {
      if((k + 1 < i) && (t[k + 1].x1 > t[k].x1))
        m = k + 1;
      else
        m = k;
      if(t[m].x1 <= t[j].x1) break;
      swap(t[j], t[m]);
      j = m; k = j + j;
    }
  }

}

int main()
{
    ios_base::sync_with_stdio(0);
    int n,w,y1,y2,t,x1,x2;
    cin>>t;
    for(int f=0;f<t;f++)
    {
        cin>>n>>w;
        for(int i=1;i<=n;i++)
        {
            poczatkowo[i].nr=i;
            cin>>x1>>y1>>x2>>y2;
            poczatkowo[i].x1=min(x1,x2);
            poczatkowo[i].h=abs(y2-y1);
        }
        for(int i=1;i<=n;i++)
        {
            koncowo[i].nr=i;
            cin>>x1>>y1>>x2>>y2;
            koncowo[i].x1=min(x1,x2);
            koncowo[i].h=abs(y2-y1);
        }
        for(int i=1;i<=n;i++)
            szczeliny[i]=w-poczatkowo[i].h;

        sortowanie(n,poczatkowo);
        sortowanie(n,koncowo);

        for(int i=1;i<=n;i++)
        {
            gdzie_jest[poczatkowo[i].nr]=i;
        }
        bool spr=1;
        for(int i=1;i<=n && spr;i++)
        {
            for(int j=1;j<=n;j++)
                nbufor[j]=0;

            for(int j=i+1;j<=n;j++)
            {
                nbufor[koncowo[j].nr]=1;
            }
            for(int j=gdzie_jest[koncowo[i].nr]+1;j<=n;j++)
            {
                nbufor[poczatkowo[j].nr]=0;
            }
            for(int j=1;j<=n;j++)
            {
                if(nbufor[j])
                {
                    if(szczeliny[j]  <  koncowo[i].h )
                    {
                        spr=0;
                        break;
                    }
                }
            }
        }
        if(spr)
            cout<<"TAK"<<endl;
        else
            cout<<"NIE"<<endl;
    }

    return 0;
}