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
#include <cstdio>
#include <cassert>
#include <set>
#include <algorithm>

const int M = 2013;
const int inf = ((int)2e9);

struct point {
	point(long long _x, long long _y, long long _i)
 	  : x(_x), y(_y), i(_i) {}
	point() : x(0), y(0), i(0) {}

	long long	x, y, i;

	bool operator<(const point& other) const {
		if (x != other.x) return x < other.x;
		return y < other.y;
	}

	point& operator=(const point& other) {
		x = other.x;
		y = other.y;
		i = other.i;
		return *this;
	}
} t[M];

int n, ret[M], max_c[M];

bool go(long long min_y, long long max_y, long long w) {
	if (max_y <= w) return false;
	//printf("go %lld %lld\n",min_y, max_y);
	std::set<point> s;
	s.insert(point(t[0].x, min_y, max_y - min_y));
	int next_point = 0;
	while (!s.empty()) {
		long long x = s.begin()->x;
		long long ya = s.begin()->y;
		long long yb = ya;
		while (!s.empty() && s.begin()->x == x && s.begin()->y == yb) {
			yb = s.begin()->y + s.begin()->i;
			s.erase(s.begin());
		}
		if (s.empty() && next_point == n && ya == min_y && yb == max_y) return true;
		int i = next_point;
		while (i < n && t[i].x == x && t[i].y >= ya && t[i].y < yb)
			i++;
		//printf("%lld %lld %lld :: %d %d\n", x, ya, yb, next_point, i);
		if (i == next_point || t[next_point].y != ya) return false;
		long long dd = 0, dy = 0;
		for (int j = next_point; j < i; j++) {
			long long d = (j == i-1 ? yb : t[j+1].y) - t[j].y;
			if (d > inf || d < 1) return false;
			ret[t[j].i] = d;
			if (d != dd) {
				if (dd) s.insert(point(t[j-1].x + dd, dy, t[j-1].y - dy + dd));
				dd = d;
				dy = t[j].y;
			}
			//s.insert(point(t[j].x + d, t[j].y, d));
		}
		if (dd) s.insert(point(t[i-1].x + dd, dy, t[i-1].y - dy + dd));
		next_point = i;
	}
	return false;
}

bool tc() {
	scanf("%d",&n);
	for (int i = 0; i < n; i++) {
		scanf("%lld %lld",&t[i].x, &t[i].y);
		t[i].i = i;
	}
	std::sort(t, t+n);
	long long min_y = t[0].y;
	long long max_y = t[0].y;
	for (int i = 0; i < n; i++) {
		min_y = std::min(min_y, t[i].y);
		max_y = std::max(max_y, t[i].y);
	}

	if (t[0].x == t[n-1].x || min_y == max_y) {
		// n identical squares.
		int s = n > 1 ? t[1].y-t[0].y+t[1].x-t[0].x : 1;
		return go(t[0].y, t[n-1].y + s, t[n-1].y);
	}
	
	for (int i = 0; i < n; i++) {
		max_c[i] = inf;
		for (int j = i+1; j < n; j++) {
			if(t[j].x >= t[i].x && t[j].y >= t[i].y)
				max_c[i] = std::min(max_c[i], std::max<int>(t[j].x-t[i].x, t[j].y-t[i].y));
		}
	}
	int i = 0;
	while(i+1 < n && t[i+1].x == t[0].x) i++;
	long long last = 0;
	for (int j = i+1; j < n; j++) {
		long long c = t[j].x - t[i].x;
	//	printf("%lld\n", c);
	  if (c > last && max_c[i] >= c && t[j].y + max_c[j] >= t[i].y + c) {
			last = c;
			if (go(min_y, t[i].y+c, max_y)) {
				return true;
			}
		}
	}
	for (int j = 0; j < n; j++) last = std::max(last, t[j].x-t[i].x);
	for (int j = 0; j < n; j++) if (t[j].y < t[i].y) {
		long long cj = t[i].y - t[j].y;
		long long ci = cj + t[j].x - t[i].x;
		if (ci <= max_c[i] && cj <= max_c[j] && ci > last) {
			if (go(min_y, t[i].y + ci, max_y)) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	int tt;
	scanf("%d",&tt);
	for (int i = 0; i < tt; i++) {
		if (tc()) {
			printf("TAK");
			for (int j = 0; j < n; j++)
				printf(" %d", ret[j]);
			printf("\n");
		}
	 	else puts("NIE");
	}
}