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
#include<bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct punkt {
	int x;
	int y;
	int bok;
};
void solve() {
	int n;
	scanf("%d", &n);
	if(n==1){ printf("TAK 1\n"); return;}
	pair<int, int> p[n];
	int odp[n];
	int lewy = INF, maksprawy = -1;
	int dolny = INF, maksgorny = -1;
	for(int i = 0; i < n; i++) {
		scanf("%d%d", &p[i].second, &p[i].first);
		lewy = min(lewy, p[i].second);
		dolny = min(dolny, p[i].first);
		maksprawy = max(maksprawy, p[i].second);
		maksgorny = max(maksgorny, p[i].first);
		odp[i] = 0;
	}
	vector<int> naKoniec;
	for(int i = 0; i < n; i++) {
		int minOdl = INF;
		for(int j = 0; j < n; j++) {
			if(i==j) continue;
			int x1 = p[i].second, y1 = p[i].first;
			int x2 = p[j].second, y2 = p[j].first;
			if(x2>x1 and y2>y1) minOdl = min(max(x2-x1, y2-y1), minOdl);
			else if(x2==x1 and y2>y1) minOdl = min(minOdl, y2-y1);
			else if(x2>x1 and y2==y1) minOdl = min(minOdl, x2-x1);
			
		}
		if(minOdl==INF) naKoniec.push_back(-i);
		else {
			odp[i] = minOdl;
			maksprawy = max(maksprawy, p[i].second+minOdl);
			maksgorny = max(maksgorny, p[i].first+minOdl);
		}
	}
	sort(naKoniec.begin(), naKoniec.end());
	for(int i = 0; i < naKoniec.size(); i++) naKoniec[i] = abs(naKoniec[i]);
	for(int i = 0; i < naKoniec.size(); i++) {
			int i1 = naKoniec[i];
			int o1 = min(maksprawy-p[i1].second, maksgorny-p[i1].first);
			if(o1==0) o1 = max(maksprawy-p[i1].second, maksgorny-p[i1].first);
			odp[i1] = o1;
			maksprawy = max(maksprawy, o1+p[i1].second);
			maksgorny = max(maksgorny, o1+p[i1].first);
				

	}
	int A = maksprawy-lewy, B = maksgorny-dolny;
	int pole = A*B;
	for(int i = 0; i < n; i++) {
		pole -= odp[i]*odp[i];
	}
	if(pole==0) {
		printf("TAK ");
		for(int i = 0; i < n; i++) {
			printf("%d ", odp[i]);
		}
		printf("\n");
	}
	else printf("NIE\n");
}
int main() {
	int t;
	scanf("%d", &t);
	while(t--) solve();
}