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
117
118
119
120
121
122
123
//#define DEBUG

#include <algorithm>
#include <vector>
#include <cstdio>
#include <iterator>

#ifdef DEBUG
#define tracef(fmt, ...) \
        do { printf("%s:%d:%s(): " fmt "\n", __FILE__, \
                                __LINE__, __func__, ## __VA_ARGS__); } while (0)
#else
#define tracef(fmt, ...)
#endif

#define MAX_INT 1000000009
#define MIN_INT 0

int min_value_comparer(int a, int referenceValue)
{
  return a - referenceValue;
}

int max_value_comparer(int a, int referenceValue)
{
  return referenceValue - a;
}

#define is_new_extreme(a) ((a) < 0)
#define is_same_extreme(a) ((a) == 0)

template<int (*comparer)(int, int), int StartValue>
class ExtremeSelector
{
public:
  ExtremeSelector()
  {
    reset();
  }

  void push_back(int id, int data)
  {
    int ret = comparer(data, extremeValue);
    if (is_new_extreme(ret))
    {
      ids.clear();
      ids.push_back(id);
      extremeValue = data;
    }
    else if (is_same_extreme(ret))
    {
      ids.push_back(id);
    }
    else
    {
      if (ids.empty())
      {
        tracef("ERROR: No elements added, no element is extreme.");
      }
    }
  }

  void reset()
  {
    ids.clear();
    extremeValue = StartValue;
  }

  std::vector<int> ids;
private:
  int extremeValue;
};

typedef ExtremeSelector<min_value_comparer, MAX_INT> MinSelector;
typedef ExtremeSelector<max_value_comparer, MIN_INT> MaxSelector;

void sort(std::vector<int>& v)
{
  std::sort(v.begin(), v.end());
}

void set_intersection(const std::vector<int>& a, const std::vector<int>& b, std::vector<int>& result)
{
  std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(result));
}

int main()
{
  int t;
  scanf("%d", &t);
  MinSelector minW, minH;
  MaxSelector maxW, maxH;
  while (t--)
  {
    minW.reset();
    maxW.reset();
    minH.reset();
    maxH.reset();
    int n;
    scanf("%d", &n);
    for (int id = 0; id < n; id++)
    {
      int w1, w2, h1, h2;
      scanf("%d%d%d%d", &w1, &w2, &h1, &h2);
      minW.push_back(id, w1);
      maxW.push_back(id, w2);
      minH.push_back(id, h1);
      maxH.push_back(id, h2);
    }
    sort(minW.ids);
    sort(maxW.ids);
    sort(minH.ids);
    sort(maxH.ids);
    std::vector<int> tmp, result;
    set_intersection(minW.ids, maxW.ids, result);
    set_intersection(result, minH.ids, tmp);
    result.clear();
    set_intersection(tmp, maxH.ids, result);
    bool ret = !result.empty();
    printf(ret ? "TAK\n" : "NIE\n");
  }
  return 0;
}