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
#include<bits/stdc++.h>
using namespace std;

int t, n, ups;
long long v, a, b, dwa = 2, m_left, t_left, E_left;
vector<pair<long long,long long> >v1;
vector<pair<long long,long long> >v2;

int main() {
	
	ios_base::sync_with_stdio(0);
	cin >> t;
	for(int q = 0; q < t; q++) {
		cin >> n;
		for(int i = 0; i < n; i++) {
			cin >> v >> a >> b;
			a *= dwa, b *= dwa;
			v1.push_back(make_pair(a,v));
			v2.push_back(make_pair(b,v));
			//cout << "AA";
		}
		
		v1.push_back(make_pair(0,0));
		v2.push_back(make_pair(0,0));
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		reverse(v1.begin(), v1.end());
		reverse(v2.begin(), v2.end());
		for(int i = 0; i < (int)v1.size()-1; i++) {
			if(v1[i].first < v2[i].first) {
				//cout << i << ": " << v1[i].first << " " << v2[i].first << " NIE\n", ups++;
				cout << "NIE\n", ups++;
				break;
			}
			E_left = v1[i].first * v1[i].second + v1[i+1].first * v1[i+1].second - v2[i].first * v2[i].second;
			m_left = v1[i].second + v1[i+1].second - v2[i].second;
			//cout << E_left << " " << m_left << " " << t_left << "\n";
			if((E_left && !m_left) || E_left < 0) {
				cout << "NIE\n", ups++;
				break;
			}
			if(m_left) t_left = E_left / m_left;
			
			v1[i+1].second = m_left, v1[i+1].first = t_left;
		}
		v1.clear(), v2.clear();
		if(!ups) cout << "TAK\n";
		ups = 0;
	}
	return 0;
}