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
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

const static int LOWER_BOUND = 1;
const static int UPPER_BOUND = 1000000000;


inline void recompute(bool test, set<int> & s, int& value, int tmp, int i) {
  if (value == tmp) {
      s.insert(i);
  } else if (test) {
    s.clear();
    s.insert(i);
    value = tmp;
  }
}

inline void setUnion(const set<int> & s1, const set<int> & s2, set<int> & so) {
  set<int>::const_iterator it1 = s1.begin(), it2 = s2.begin();
  while (it1 != s1.end() && it2 != s2.end()) {
    if (*it1 == *it2) {
      so.insert(*it1);
      ++it1; ++it2;
    } else if (*it1 < *it2) {
      ++it1;
    } else {
      ++it2;
    }
  }
}


bool test() {
  int n;
  int tmp;
  int wMin = UPPER_BOUND, wMax = LOWER_BOUND, 
      hMin = UPPER_BOUND, hMax = LOWER_BOUND;
  set<int> wMinSet, wMaxSet, hMinSet, hMaxSet;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    // Mininal width
    cin >> tmp;
    recompute(wMin > tmp, wMinSet, wMin, tmp, i);
    
    // Maximal width
    cin >> tmp;
    recompute(wMax < tmp, wMaxSet, wMax, tmp, i);
    
    // Mininal height
    cin >> tmp;
    recompute(hMin > tmp, hMinSet, hMin, tmp, i);
    
    // Maximal height
    cin >> tmp;
    recompute(hMax < tmp, hMaxSet, hMax, tmp, i);
  }
  
  set<int> stmp1;
  set<int> stmp2;
  set<int> stmp3;
  setUnion(wMinSet, wMaxSet, stmp1);
  setUnion(stmp1, hMinSet, stmp2);
  setUnion(stmp2, hMaxSet, stmp3);
  
  return !stmp3.empty();
}


int main() {
  cin.sync_with_stdio(false);
  int iter;
  cin >> iter;
  for (int i = 0; i < iter; ++i) {
    cout << (test() ? "TAK" : "NIE") << endl;
  }  
  return 0;
}