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
124
125
126
127
128
129
#include <stdio.h>
#include <stdlib.h>

#define xint64 long long
#define MAXN 102400

int n;
int l[MAXN];
int a[MAXN];
int b[MAXN];
int ix[MAXN];

typedef struct {
  int t;
  xint64 v;
} t_pair;

int ip = 0;
t_pair pairs[2*MAXN];

int cmp(const void* a1, const void* a2) {
  int i1 = *((const int*) a1);
  int i2 = *((const int*) a2);
  if (pairs[i1].t!=pairs[i2].t)
    return pairs[i1].t-pairs[i2].t;
  return pairs[i1].v-pairs[i2].v;
}

void norm(int l, int r) {
  xint64 s = 0;
  for (int i=l;i<=r;i++) {
    s += pairs[ix[i]].v;
    pairs[ix[i]].v = 0;
  }
  pairs[ix[r]].v = s;
}

void show() {
  for (int i=0;i<ip;i++)
    printf("%d %d\n", pairs[ix[i]].t, pairs[ix[i]].v);
  printf("\n");
}

xint64 balance() {
  xint64 s = 0;
  for (int i=0;i<ip;i++)
    s += ((xint64)pairs[ix[i]].t) * pairs[ix[i]].v;
  return s;
}

int showE() {
  xint64 eu = 0;
  int lu = 0;
  xint64 ed = 0;
  int ld = 0;
  for (int i=0;i<ip;i++) {
    if (lu>=ld && ed+(lu-ld)*(((xint64)pairs[ix[i]].t))>eu)
      return 0;
    if (pairs[ix[i]].v<0) {
      ed -= ((xint64)pairs[ix[i]].t) * pairs[ix[i]].v;
      ld -= pairs[ix[i]].v;
    } else {
      eu += ((xint64)pairs[ix[i]].t) * pairs[ix[i]].v;
      lu += pairs[ix[i]].v;
    }
    if (lu>=ld && ed+(lu-ld)*(1+((xint64)pairs[ix[i]].t))>eu)
      return 0;
    //printf("%d %d l:%d, e:%lld vs l:%d, e:%lld\n", pairs[ix[i]].t, pairs[ix[i]].v, lu, eu, ld, ed);
  }
  //printf("\n");
  return 1;
}

void empty() {
  int j = 0;
  for (int i=0;i<ip;i++) {
    if (pairs[ix[i]].v!=0) {
      pairs[ix[j]].v = pairs[ix[i]].v;
      pairs[ix[j]].t = pairs[ix[i]].t;
      j++;
    }
  }
  ip = j;
}

int main() {
  int k;
  scanf("%d", &k);
  for (int i=0;i<k;i++) {
    scanf("%d", &n);
    for (int i=0;i<n;i++)
      scanf("%d%d%d", &l[i], &a[i], &b[i]);
    ip = 0;
    for (int i=0;i<n;i++) {
      ix[ip] = ip;
      pairs[ip].t = a[i];
      pairs[ip].v = -l[i];
      ip++;
      ix[ip] = ip;
      pairs[ip].t = b[i];
      pairs[ip].v = l[i];
      ip++;
    }
    qsort(ix, ip, sizeof(int), cmp);
    //show();
    int lix = 0;
    for (int i=0;i<ip;i++) {
      if (pairs[ix[i]].t!=pairs[ix[lix]].t) {
        norm(lix, i-1);
        lix = i;
      }
    }
    norm(lix, ip-1);
    //show(); 
    empty();
    if (ip==0) {
      printf("TAK\n");
      continue ;
    }
    if (0!=balance() || pairs[ix[0]].v>0 || pairs[ix[ip-1]].v>0) {
      printf("NIE\n");
      continue ;
    }
    if (showE())
      printf("TAK\n");
    else
      printf("NIE\n");    
  }
}