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
#include <cstdio>
#include <algorithm>

using namespace std;

#define f first
#define s second

const int MAXN = 1e5 + 3;

pair<long long, long long> t1[MAXN];
pair<long long, long long> t2[MAXN];

int main() {
    int z, n, pnt;
    long long wyn1, wyn2;
    long long poj1, poj2;
    bool por;
    scanf("%d", &z);
    while (z--) {
        wyn1 = wyn2 = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld %lld %lld", &t1[i].s, &t1[i].f, &t2[i].f);
            t2[i].s = t1[i].s;
            wyn1 += t1[i].s * t1[i].f;
            wyn2 += t2[i].s * t2[i].f;
        }
        if (wyn1 != wyn2) {
            printf("NIE\n");
            continue;
        }
        sort(t1 + 1, t1 + n + 1);
        sort(t2 + 1, t2 + n + 1);
        wyn1 = wyn2 = 0;
        poj1 = poj2 = 0;
        pnt = 0;
        por = false;
        t1[n + 1] = {0, 0};
        for (int i = 1; i <= n; i++) {
            wyn2 += t2[i].f * t2[i].s;
            poj2 += t2[i].s;
            while (t1[pnt + 1].s + poj1 <= poj2) {
                pnt++;
                wyn1 += t1[pnt].f * t1[pnt].s;
                poj1 += t1[pnt].s;
            }
            if (wyn1 + t1[pnt + 1].f * (poj2 - poj1) > wyn2) {
                por = true;
                break;
            }
        }
        if (por) {
            printf("NIE\n");
            continue;
        }
        pnt = n + 1;
        wyn1 = wyn2 = 0;
        poj1 = poj2 = 0;
        for (int i = n; i > 0; i--) {
            wyn2 += t2[i].f * t2[i].s;
            poj2 += t2[i].s;
            while (t1[pnt - 1].s + poj1 <= poj2) {
                pnt--;
                wyn1 += t1[pnt].f * t1[pnt].s;
                poj1 += t1[pnt].s;
            }
            if (wyn1 + t1[pnt - 1].f * (poj2 - poj1) < wyn2) {
                por = true;
                break;
            }
        }
        printf(por ? "NIE\n" : "TAK\n");
    }
    return 0;
}