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 #include using namespace std; typedef long long ll; const int MAX_A = 1e6; const int MAX_B = 1e6; int n, q, currA, currB; ll sum1, sum2, a, b, c; ll tabA[MAX_A + 5], tabB[MAX_B + 5]; vector idA, idB; bool t; void Clear(){ for(auto i : idA){ tabA[i] = 0ll; } for(auto i : idB){ tabB[i] = 0ll; } idA.clear(); idB.clear(); } bool Solve(){ Clear(); sum1 = 0; sum2 = 0; t = true; cin >> n; for(int i=0; i> c >> a >> b; sum1 += a * c; sum2 += b * c; tabA[a] += c; tabB[b] += c; idA.push_back(a); idB.push_back(b); } if(sum1 != sum2){ return false; } sort(idA.begin(), idA.end()); idA.erase(unique(idA.begin(), idA.end()), idA.end()); sort(idB.begin(), idB.end()); idB.erase(unique(idB.begin(), idB.end()), idB.end()); currA = idA.size() - 1; currB = idB.size() - 1; sum1 = 0; while(currA >= 0 or currB >= 0){ a = min(tabA[idA[currA]], tabB[idB[currB]]); b = idA[currA] - idB[currB]; tabA[idA[currA]] -= a; tabB[idB[currB]] -= a; sum1 += b * a; if(sum1 < 0){ t = false; break; } if(!tabA[idA[currA]]){ currA --; } if(!tabB[idB[currB]]){ currB --; } } t = ((!sum1) and t); return t; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> q; while(q --){ cout << (Solve() ? "TAK\n" : "NIE\n"); } return 0; }