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
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <numeric>
#include <algorithm>

template <class I>
struct Ratio {
	I num, denom;

	Ratio(I num) : num(num), denom(1) {}
	Ratio(I num, I denom) {
		if (denom < 0) {
			num = -num;
			denom = -denom;
		}
		I div = std::gcd(num, denom);
		this->num = num / div;
		this->denom = denom / div;
	}

	bool operator== (const Ratio& r) const { return num == r.num && denom == r.denom; }
	bool operator< (const Ratio& r) const { return num * r.denom < r.num * denom; }
	bool operator> (const Ratio& r) const { return num * r.denom > r.num * denom; }

	Ratio operator+(const Ratio& r) const { return Ratio(num * r.denom + denom * r.num, denom * r.denom); }
	Ratio operator-(const Ratio& r) const { return Ratio(num * r.denom - denom * r.num, denom * r.denom); }
	Ratio operator*(const Ratio& r) const { return Ratio(num * r.num, denom * r.denom); }
	Ratio operator/(const Ratio& r) const { return Ratio(num * r.denom, denom * r.num); }
};

using RatioI = Ratio<int64_t>;

struct Cup {
	RatioI liters;
	RatioI temp;
	RatioI target_temp;

	Cup(): liters(0), target_temp(0), temp(0) {}
	Cup(int liters, int temp, int target_temp): liters(RatioI(liters)), temp(RatioI(temp)), target_temp(RatioI(target_temp)) {}

	bool just_right() const { return temp == target_temp; }
	bool needs_warming() const { return temp < target_temp; }
	bool needs_cooling() const { return temp > target_temp; }

	bool mix(Cup& cup2) {
		if (!((needs_cooling() && cup2.needs_warming()) || (needs_warming() && cup2.needs_cooling()))) {
			return false;
		}
		RatioI liters1 = (target_temp - temp) / (cup2.temp - temp) * liters;
		RatioI liters2 = (cup2.target_temp - cup2.temp) / (temp - cup2.temp) * cup2.liters;
		RatioI mix_liters = std::min(std::min(liters1, liters2), std::min(liters, cup2.liters));

		RatioI new_temp1 = (liters - mix_liters) / liters * temp + mix_liters / liters * cup2.temp;
		RatioI new_temp2 = mix_liters / cup2.liters * temp + (cup2.liters - mix_liters) / cup2.liters * cup2.temp;
		
		this->temp = new_temp1;
		cup2.temp = new_temp2;
		return true;
	}
};

bool check(std::vector<Cup>& cups) {
	for (size_t i = 0; i < cups.size() - 1; i++) {
		Cup& cup = cups.at(i);

		for (size_t j = i + 1; j < cups.size(); j++) {
			if (cup.just_right()) {
				break;
			}
			cup.mix(cups.at(j));
		}
		if (!cup.just_right()) {
			return false;
		}
	}
	return cups.back().just_right();
}

int main() {
	int test_count;
	std::scanf("%d", &test_count);

	for (int test_i = 0; test_i < test_count; test_i++) {
		int cup_count, liters, temp, target_temp;
		std::scanf("%d", &cup_count);
		std::vector<Cup> cups = std::vector<Cup>();
		cups.reserve(cup_count);

		for (int cup_i = 0; cup_i < cup_count; cup_i++) {
			scanf("%d %d %d", &liters, &temp, &target_temp);
			cups.push_back(Cup(liters, temp, target_temp));
		}

		if (check(cups)) {
			printf("TAK\n");
		} else {
			printf("NIE\n");
		}
	}
	return 0;
}