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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
using namespace std;

bool isOverlap(long long x1, long long y1, long long w1, long long x3, long long y3, long long w2) {
	long long x2 = x1 + w1;
	long long y2 = y1 + w1;
	long long x4 = x3 + w2;
	long long y4 = y3 + w2;

//	if(x3 >= x2 || y3 >= y2 || x1 >= x4 || y1 >= y4) return false;

	if(x3 > x1 && x3 < x2 && y3 > y1 && y3 < y2) return true;
	if(x4 > x1 && x4 < x2 && y4 > y1 && y4 < y2) return true;
	if(x3 > x1 && x3 < x2 && y4 > y1 && y4 < y2) return true;
	if(x4 > x1 && x4 < x2 && y3 > y1 && y3 < y2) return true;

	return false;
}

void testMosaic() {
	int n;
	long long x[2000], y[2000];
	long long min[2000];
	long long xr[2000], yr[2000];
	for(int i = 0; i < 2000; i++) {
		x[i] = 0;
		y[i] = 0;
		min[i] = 0;
		xr[i] = 0;
		yr[i] = 0;
	}

	cin >> n;

	if(n == 1) {
		cout << "TAK 1 1" << endl;
		return;
	}

	for(int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(i == j) continue;
			if(x[i] == x[j] && y[j] > y[i]) {
				if(min[i] == 0 || min[i] > y[j] - y[i]) min[i] = y[j] - y[i];
			}
			if(y[i] == y[j] && x[j] > x[i]) {
				if(min[i] == 0 || min[i] > x[j] - x[i]) min[i] = x[j] - x[i];
			}
		}
	}

	for(int i = 0; i < n; i++) {
		if(min[i] == 0) continue;
		for(int j = 0; j < n; j++) {
			if(i == j) continue;
			if(isOverlap(x[i], y[i], min[i], x[j], y[j], min[j])) {
				if((y[j] - y[i]) > (x[j] - x[i])) {
					min[i] = (y[j] - y[i]);
				}
				else {
					min[i] = (x[j] - x[i]);
				}

			}
			xr[i] = x[i] + min[i];
			yr[i] = y[i] + min[i];
		}
	}

	long long left = x[0], bottom = y[0], right = x[0], top = y[0];

	for(int i = 0; i < n; i++) {
		if(x[i] < left) left = x[i];
		if(y[i] < bottom) bottom = y[i];
		if(xr[i] != 0 && xr[i] > right) right = xr[i];
		if(yr[i] != 0 && yr[i] > top) top = yr[i];
	}

	for(int i = 0; i < n; i++) {
		if(xr[i] == 0 && yr[i] == 0) {
			long long r = right - x[i];
			long long t = top - y[i];

			if((r != 0 && r <= t) || (r !=0 && t == 0)) {
				xr[i] = x[i] + r;
				yr[i] = y[i] + r;
			}
			else if((t != 0 && t <= r) || (t != 0 && r == 0)){
				xr[i] = x[i] + t;
				yr[i] = y[i] + t;
			}
			if(xr[i] > right) right = xr[i];
			if(yr[i] > top) top = yr[i];
		}
	}

	long long field = (top - bottom) * (right - left);
	long long distance = (2 * (top - bottom)) + (2 * (right - left));

	long long field_total = 0;
	for(int i = 0; i < n; i++) {
		field_total += (xr[i]-x[i]) * (yr[i]-y[i]);
	}

	if(field != field_total) {
		cout << "NIE" << endl;
		return;
	}
	else {
		long long distance_total = 0;
		for(int i = 0; i < n; i++) {
			if(x[i] == left) {
				distance_total += (xr[i] - x[i]);
			}
			if(y[i] == bottom) {
				distance_total += (xr[i] - x[i]);
			}
			if(xr[i] == right) {
				distance_total += (xr[i] - x[i]);
			}
			if(yr[i] == top) {
				distance_total += (xr[i] - x[i]);
			}
		}
		if(distance != distance_total) {
			cout << "NIE" << endl;
			return;
		}
		else {
			cout << "TAK ";
			for(int i = 0; i < n; i++) {
				cout << xr[i] - x[i];
				if(i < n-1) cout << " ";
			}
			cout << endl;
		}
	}
}

int main() {
	int t;
	cin >> t;

	for(int i = 0; i < t; i++) {
		testMosaic();
	}

	return 0;
}