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
#include <bits/stdc++.h>
#define N 100007
using namespace std;
long long t, n,a,b,l;
pair<long long, long long> poczatkowe[N], koncowe[N];

pair<long long, long long> aktualny, pozadany;
pair<long long, long long> operator+(const pair<long long, long long> &a,
    const pair<long long, long long> &b) {
  long long nowa_objetosc = a.second + b.second;
  long long nowa_temperatura = a.first + b.first;
  return make_pair(nowa_temperatura, nowa_objetosc);
}

bool cmp(const pair<long long, long long> &a,
    const pair<long long, long long> &b) {
  if (b.second * a.first != a.second * b.first) {
    return a.first * b.second < b.first * a.second;
  }
  return a < b;
}
long long laczna_energia;
int zuzyte;
bool skonczone;
bool przelej(int indeks, bool od_dolu) {
  //if(zuzyte >= n) { printf("Cos poszlo nie tak1!\n"); return false; }
  pozadany = pozadany + koncowe[indeks];
  while (pozadany.second > aktualny.second + poczatkowe[zuzyte].second) {
    aktualny = aktualny + poczatkowe[zuzyte];
    zuzyte += 1;
  }
  //printf("Mam %lld objetosci i %lld temperatury\n", aktualny.second, aktualny.first);
  //printf("Chce miec %lld objetosci i %lld temperatury\n", pozadany.second, pozadany.first);
  //if(zuzyte >= n) { printf("Cos poszlo nie tak!\n"); return false; }
  long long brakujaca_objetosc = pozadany.second - aktualny.second;
  //printf("Moge dolac id %d: %lld %lld\n", zuzyte, brakujaca_objetosc, poczatkowe[zuzyte].first);
  pair<long long, long long> po_dolaniu = aktualny + make_pair(poczatkowe[zuzyte].first, brakujaca_objetosc);
  //printf("Po dolaniu bede mial %lld objetosci i %lld temperatury\n", po_dolaniu.second, po_dolaniu.first);
  //printf("Chce miec %lld %lld\n", pozadany.second, pozadany.first);
  if (od_dolu) {
    if ((poczatkowe[zuzyte].first/poczatkowe[zuzyte].second) * brakujaca_objetosc > (pozadany.first - aktualny.first)) {
      return false;
    }
  } else {
    if ((poczatkowe[zuzyte].first/poczatkowe[zuzyte].second) * brakujaca_objetosc < (pozadany.first - aktualny.first)) {
      return false;
    }
  }
  return true;
}

int main() {
  scanf("%lld", &t);
  while(t--){
    scanf("%lld", &n);
    aktualny = make_pair(0, 0);
    pozadany = make_pair(0, 0);
    zuzyte = 0;
    laczna_energia = 0LL;
    for (int i = 0; i < n; i++) {
      scanf("%lld%lld%lld", &l, &a, &b);
      poczatkowe[i] = make_pair(a * l, l);
      koncowe[i] = make_pair(b * l, l);
      laczna_energia += l * (b - a);
    }
    if (laczna_energia != 0LL) {
      printf("NIE\n");
      continue;
    }
    sort(poczatkowe, poczatkowe+n, cmp);
    sort(koncowe, koncowe+n, cmp);
    //printf("poczatkowe: ");
    for(int i=0; i <n ;i++){
      //printf("%lld ", poczatkowe[i].first);
    }
    //printf("\n");
    for(int i=0; i <n ;i++){
      //printf("%lld ", poczatkowe[i].second);
    }

    //printf("\nkoncowe: ");
    for(int i=0; i <n ;i++){
      //printf("%lld ", koncowe[i].first);
    }
    //printf("\n");
    skonczone = false;
    for(int i = 0; i < n; i++) {
      //printf("i%d, zuzyte %d\n", i, zuzyte);
      if (!przelej(i, true)){
        skonczone = true;
        printf("NIE\n");
        break;
      }
    }
    if (skonczone) continue;
    reverse(poczatkowe, poczatkowe+n);
    reverse(koncowe, koncowe+n);
    zuzyte = 0;
    aktualny = make_pair(0, 0);
    pozadany = make_pair(0, 0);
    for(int i = 0; i < n; i++) {
      //printf("i%d, zuzyte %d\n", i, zuzyte);
      if (!przelej(i, false)){
        skonczone = true;
        printf("NIE\n");
        break;
      }
    }
    if (skonczone) continue;
    printf("TAK\n");
  }
}