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

using namespace std;

struct Point{
	int x;
	int y;
	int l = 0;
};

bool comparePoints(Point p1, Point p2){
	if(p1.y == p2.y) return p1.x < p2.x;
	else return p1.y < p2.y;
}


int main(){
	int t = 0;
	cin >> t;
	
	for(int j = 0; j < t; j++){
		int n = 0;
		cin >> n;
		Point *pts = new Point[n];
		
		for(int i = 0; i < n; i++){
			Point p;
			cin >> p.x >> p.y;
			pts[i] = p;
		}
		
		sort(pts, pts+n, comparePoints);
		
		vector<vector<Point>> points;
		int lastY = -1;
		int Y = -1;
		for(int i = 0; i < n; i++){
			if(lastY != pts[i].y){
				lastY = pts[i].y;
				Y++;
				points.push_back(vector<Point>());
			}
			
			points[Y].push_back(pts[i]);
		}
		
		int maxX;
		int maxY;
		
		for(int y = 0; y < points.size(); y++){
			for(int x = 0; x < points[y].size(); x++){
				Point &p = points[y][x];
				
				if(x < points[y].size()-1){
					p.l = points[y][x+1].x - p.x;
				}
				else if(y < points.size()-1){
					p.l = points[y+1][0].y - p.y;
					maxX = p.l + p.x;
				}
				else{
					p.l = maxX - p.x;
				}
			}
		}
		
		int pole = 0;
		for(int y = 0; y < points.size(); y++){
			for(int x = 0; x < points[y].size(); x++){
				pole += (points[y][x].l * points[y][x].l);
			}
		}
		int px, py;
		px = maxX - points[0][0].x;
		py = points[points.size()-1][0].l + (points[points.size()-1][0].y - points[0][0].y);
		
		if(pole != px*py){
			cout << "NIE\n";
			continue;
		}
		cout << "TAK ";
		
		for(int y = 0; y < points.size(); y++){
			for(int x = 0; x < points[y].size(); x++){
				cout << points[y][x].l << ' ';
			}
		}
	
		cout << '\n';
	}

	return 0;
}