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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point
{
	long long x, y, a;
	int id;
	
	Point() {}
	
	Point(long long  _x, long long _y, int _id) : x(_x), y(_y), id(_id) {}
};


bool cmp(Point a, Point b)
{
	return (a.y == b.y) ? a.x < b.x : a.y < b.y;
}

vector <Point> data;
vector <Point> vec;

long long a1, a2, b1, b2;
int n, t;

bool prog()
{
	a2 = b2 = 0;
	a1 = vec[0].x;
	b1 = vec[0].y;
	int i, j;
	long long k, x, y, x1, y1, a;
	
	for(i = 0; i < vec.size(); ++i)
	{
		x = vec[i].x;
		y = vec[i].y;
		
		j = i + 1;
		while(vec[j].y == y && j < n) ++j;
		if(j == n) y1 = -1;
		else y1 = vec[j].y;
		
		
		x1 = 2000000009;
		for(j = 0; j < data.size(); ++j)
		if(data[j].id != vec[i].id && data[j].x > x && data[j].y >= y && data[j].x < x1)
		x1 = data[j].x;
		if(x1 == 2000000009) x1 = -1;
		
		if(x1 - vec[i].x != y1 - vec[i].y && x1 != -1 && y1 != -1) return false;
		else if(x1 == -1 && y1 == -1)
		{
			a = a2 - x;
		}
		else if( x1 == -1) a = y1 - y;
		else if( y1 == -1) a = x1 - x;
		else a = x1 - x;
		vec[i].a = a;

		if(a2 < x + a) a2 = x + a;
		if(b2 < y + a) b2 = y + a;
	}
	
	for(i = 0; i < n; ++i) data[vec[i].id - 1].a = vec[i].a;
	
	unsigned long area1, area2;
	area1= (a2 - a1) * (b2 - b1);
	area2= 0;
	for(i = 0; i < n; ++i) area2 += (data[i].a * data[i].a);
	return area1 == area2;
}

int main()
{
	int i, j;
	long long x , y;
	
	cin >> t;
	while(t--)
	{
		cin >> n;
		for(i = 1; i <= n; ++i)
		{
			cin >> x >> y;
			data.push_back(Point(x, y, i));
			vec.push_back(Point(x, y, i));
		}
		sort(vec.begin(), vec.end(), cmp);
		
		if(prog())
		{
			cout << "TAK ";
			for(i = 0; i < n; ++i) cout << data[i].a << ' ';
			cout << '\n';
		}
		else cout << "NIE\n";
		
		data.clear();
		vec.clear();
	}
	
	return 0;
}