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 #include #include #include #include using namespace std; typedef vector vi; typedef pair pii; typedef long long int ll; bool solve() { int n; cin >> n; vector ap(n), bp(n); for (int i = 0; i < n; i++) { cin >> ap[i].second >> ap[i].first >> bp[i].first; bp[i].second = ap[i].second; } sort(ap.begin(), ap.end()); sort(bp.begin(), bp.end()); auto ait = ap.begin(), bit = bp.begin(); list c; while (ait != ap.end()) { int n = min(ait->second, bit->second); if (ait->first != bit->first) { c.push_back(ll(n) * ll(ait->first - bit->first)); } ait->second -= n; bit->second -= n; if (ait->second == 0) ait++; if (bit->second == 0) bit++; } auto it = c.begin(), jt = c.begin(); while (it != c.end()) { while (it != c.end() && *it == 0) it++; if (it == c.end()) break; if (*it > 0) return false; while (*it < 0) { while (jt != c.end() && *jt <= 0) jt++; if (jt == c.end()) return false; if (*jt <= -(*it)) { *it += *jt; *jt = 0; jt++; } else { *jt += *it; *it = 0; } } } return true; } int main() { ios_base::sync_with_stdio(0); int z; cin >> z; while (z--) { bool res = solve(); cout << (res ? "TAK" : "NIE") << endl; } return 0; }