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
113
114
115
116
117
118
119
120
121
122
123
#include <stdio.h>
#include <string.h>
#include <cstdlib>
// tak, tak wyglada syfiasty kod  :-D

struct cup {
  signed long long int vol;
  signed long long int temp;
};

int compare (const void* a, const void* b) {
  const cup* x = (cup*) a;
  const cup* y = (cup*) b;
  if (x->temp > y->temp) {
    return 1;
  } else if (x->temp < y->temp) {
    return -1;
  } else {
    return 0;
  }
}

/* void printCups(cup* t, int n) {
  for (int i = 0; i < n; i++) {
    printf("[%d](%llu,%llu); ", i, t[i].vol, t[i].temp);
  }
  printf("\n");
} */

int n;
cup given[101000];
cup expected[101000];
signed long long int givenSum = 0, expectedSum = 0;


int check() {
    int pointer;
    pointer = 0;
    givenSum = expectedSum = 0;
    signed long long int vol, volGiven, min;
    volGiven = given[pointer].vol;
    for (int i = 0; i < n; i++) {
      vol = expected[i].vol;
      while (vol > 0) {
        min = (vol < volGiven ? vol : volGiven);
        givenSum += min * given[pointer].temp;
        expectedSum += min * expected[i].temp;
        vol -= min;
        volGiven -= min;
        if(volGiven == 0) {
          pointer++;
          if (pointer < n) {  // XXX: wpp. albo koniec albo cos BARDZO nie-halo
            volGiven = given[pointer].vol;
          }
        }
      }
      if (givenSum > expectedSum) {
//        if (givenSum == expectedSum || pointer == n) { printf("cos zle"); }
        return 0;
      }
    }
//    printf("given = %lld expected = %lld", givenSum, expectedSum);
//    if (givenSum != expectedSum || pointer != n) { printf("cos zle"); }
    return 1;
}

int main() {
  int t;
  scanf("%d", &t);
  for (int number = 0; number < t; number ++) {
    int ret = 1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
      signed long long int l, a, b;
      scanf("%lld %lld %lld", &l, &a, &b);
      given[i].vol = l;
      given[i].temp = a;
      expected[i].vol = l;
      expected[i].temp = b;
//       givenSum += l * a;
//      expectedSum += l * b;
    }
//    printf("given = %llu expected = %llu", givenSum, expectedSum);

    qsort(given, n, sizeof(cup), compare);
//    printf("given: ");    printCups(given, n);
    qsort(expected, n, sizeof(cup), compare);

    ret = check();
    if (ret) {
      for(int i = 0; i < n; i++) {
        given[i].temp *= -1;
        expected[i].temp *= -1;
      }
      struct cup tmp;
      for(int i = 0; i < n; i++) {
        int j = n - i - 1;
        if (i < j) {
          tmp = expected[i];
          expected[i] = expected[j];
          expected[j] = tmp;
          tmp = given[i];
          given[i] = given[j];
          given[j] = tmp;
        } else {
          break;
        }
      }
//      qsort(given, n, sizeof(cup), compare);   // XXX: odwrotne sortowanie - 
  //  printf("given: ");    printCups(given, n);
//      qsort(expected, n, sizeof(cup), compare);
      ret = check();
    }
    if (ret) {
//      if (givenSum != expectedSum) { printf("cos zle"); }
      printf("TAK\n");
    } else {
//      if (givenSum == expectedSum) { printf("cos zle"); }
      printf("NIE\n");
    }
  }
  return 0;
}