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 using namespace std; const int INF = 2e9; bool solve() { int n, a, b, l; cin >> n; vector > al_read; vector > al; vector > bl; long long suma = 0, sumb = 0; for (int i = 0; i < n; i++) { cin >> l >> a >> b; suma += l * a; sumb += l * b; al_read.push_back(make_pair(a, l)); bl.push_back(make_pair(b, l)); } if (suma != sumb) { return false; } sort(al_read.begin(), al_read.end()); sort(bl.begin(), bl.end()); al = al_read; long long prefa = 0; long long prefb = 0; long long sum_pref_a = 0; long long sum_pref_b = 0; int j = 0; for (int i = 0; i < n; i++) { sum_pref_b += bl[i].second * bl[i].first; prefb += bl[i].second; while(prefa < prefb && prefa + al[j].second <= prefb) { prefa += al[j].second; sum_pref_a += al[j].second * al[j].first; j++; } sum_pref_a += (prefb - prefa) * al[j].first; al[j].second -= (prefb - prefa); prefa = prefb; if (sum_pref_a > sum_pref_b) { return false; } } al = al_read; long long sufa = 0; long long sufb = 0; long long sum_suf_a = 0; long long sum_suf_b = 0; j = n - 1; for (int i = n - 1; i >= 0; i--) { sum_suf_b += bl[i].second * bl[i].first; sufb += bl[i].second; while(sufa < sufb && sufa + al[j].second <= sufb) { sufa += al[j].second; sum_suf_a += al[j].second * al[j].first; j--; } sum_suf_a += (sufb - sufa) * al[j].first; al[j].second -= (sufb - sufa); sufa = sufb; if (sum_suf_a < sum_suf_b) { return false; } } return true; } int main() { int t; cin >> t; while (t--) { cout << (solve() ? "TAK" : "NIE") << endl; } return 0; }