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
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<long long int, long long int> input[100010];
pair<long long int, long long int> output[100010];

struct compare {
	bool operator()(const pair<long long int, long long int>& value,
		const long long int key)
	{
		return (value.first < key);
	}
	bool operator()(const long long int& key,
		const pair<long long int, long long int>& value)
	{
		return (key < value.first);
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	long long int t, n, l, a, b;

	cin >> t;

	for (int tt = 0; tt < t; tt++)
	{
		cin >> n;
		int sum1 = 0;
		int sum2 = 0;

		for (int i = 0; i < n; i++)
		{
			cin >> l >> a >> b;

			input[i] = make_pair(a, l);
			output[i] = make_pair(b, l);

			sum1 += a * l;
			sum2 += b * l;
		}

		if (sum1 != sum2)
		{
			cout << "NIE" << endl;
			continue;
		}

		long long int avg = sum1 / n;

		sort(input, input + n);
		sort(output, output + n);

		long long int mid1 = lower_bound(input, input + n, avg, compare()) - input;
		long long int mid2 = lower_bound(output, output + n, avg, compare()) - output;

		if (mid1 != mid2)
		{
			cout << "NIE" << endl;
			continue;
		}

		long long int mid_input_1 = mid1 + 1;
		long long int mid_output_1 = mid1 + 1;
		long long int tmp = 0;
		bool error = false;

		while (mid_input_1 < n && mid_output_1 < n)
		{
			long long int minn = min(input[mid_input_1].first, output[mid_output_1].first);
			if (minn == input[mid_input_1].first && input[mid_input_1].first == output[mid_output_1].first)
			{
				tmp += output[mid_output_1++].second - input[mid_input_1++].second;
			}
			else if (minn == input[mid_input_1].first)
			{
				tmp -= input[mid_input_1++].second;
			}
			else
			{
				tmp += output[mid_output_1++].second;
			}

			if (tmp < 0)
			{
				error = true;
				break;
			}
		}

		if (error)
		{
			cout << "NIE" << endl;
			continue;
		}

		long long int mid_input_2 = mid1;
		long long int mid_output_2 = mid1;
		tmp = 0;

		while (mid_input_2 >= 0 && mid_output_2 >= 0)
		{
			long long int minn = min(input[mid_input_2].first, output[mid_output_2].first);
			if (minn == input[mid_input_2].first && input[mid_input_2].first == output[mid_output_2].first)
			{
				tmp += output[mid_output_2--].second - input[mid_input_2--].second;
			}
			else if (minn == input[mid_input_2].first)
			{
				tmp -= input[mid_input_2--].second;
			}
			else
			{
				tmp += output[mid_output_2--].second;
			}

			if (tmp < 0)
			{
				error = true;
				break;
			}
		}

		if (error)
		{
			cout << "NIE" << endl;
			continue;
		}

		cout << "TAK" << endl;
	}
}