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

using namespace std;

#define ULL unsigned long long

ULL min(ULL a, ULL b) {
	return a < b ? a : b;
}

ULL max(ULL a, ULL b) {
	return a > b ? a : b;
}

vector<pair<ULL,ULL>> po;
vector<pair<ULL,ULL>> ne;
vector<int> order;
vector<int> wm;

struct comparator {
    bool operator()(const int &a, const int &b) {
    	if (po[a].first != po[b].first) {
    		return po[a].first > po[b].first;
    	}	
	    return po[a].second > po[b].second;
	}			
};

bool not_same(const pair<ULL,ULL> &a, const pair<ULL,ULL> &b) {
	return !(a.first == b.first && a.second == b.second);
}


int main() {
	ULL INF = 1000000001;
	ULL t;
	scanf("%llu", &t);
	while (t--) {
		ULL n,x,y;
		scanf("%llu", &n);

		ULL *so = new ULL[n];

		
		po.clear();
		ne.clear();
		order.clear();
		wm.clear();

		for (int i = 0; i < n; i++) {
			scanf("%llu%llu", &x, &y);
			po.push_back(make_pair(x,y));
			ne.push_back(make_pair(x,y));
			order.push_back(i);
			so[i] = 0;
		}

		sort(order.begin(), order.end(), comparator());
		for (int idx = 0; idx < n; idx++) {
			int i = order[idx];
			x = po[i].first;
			y = po[i].second;
			// printf("Szukam kumpla dla: %llu %llu z posrod: %d\n", x, y, ne.size());
			ULL a = INF;
			ULL mateidx = INF;

			for (int j = 0; j < ne.size(); j++) {
				// printf("%llu %llu !!\n", ne[j].first, ne[j].second);
				if (not_same(po[i], ne[j]) && ne[j].first >= po[i].first && ne[j].second >= po[i].second) {
					// printf(" - rozwazam %llu %llu\n", ne[j].first, ne[j].second);
					ULL la = max(ne[j].second - po[i].second, ne[j].first - po[i].first);
					if (la < a) {
						a = la;
						mateidx = j;
					}
				}
			}
			if (mateidx != INF) {
				ULL a = max(ne[mateidx].second - po[i].second, ne[mateidx].first - po[i].first);
				// printf("- kumpel: %llu %llu o boku %llu\n", ne[mateidx].first, ne[mateidx].second, a);
				so[i] = a;
				// printf(" - dodaje do zbioru %llu %llu\n", x + a, y + a);
				ne.push_back(make_pair(x + a, y + a));
			} else {
				// printf("- ni ma\n");
				wm.push_back(i);
			}
		}

		ULL minx, miny; minx = miny = INF;
		ULL maxx, maxy; maxx = maxy = 0;
		for (int i = 0; i < n; i++) {
			minx = min(minx, po[i].first);
			miny = min(miny, po[i].second);
			maxx = max(maxx, po[i].first + so[i]);
			maxy = max(maxy, po[i].second + so[i]);
		}

		for (auto it = wm.begin(); it != wm.end(); it++) {
			ULL a = max(maxy - po[*it].second, maxx - po[*it].first);
			so[*it] = a;
			maxx = max(maxx, po[*it].first + so[*it]);
			maxy = max(maxy, po[*it].second + so[*it]);
		}

		ULL area = 0;
		for (int i = 0; i < n; i++) {
			area += so[i] * so[i];
		}
		bool success = area == (maxx - minx) * (maxy - miny);
		if (success) {
			printf("TAK ");
			for (int i = 0; i < n; i++) printf("%llu ", so[i]);
			printf("\n");
		} else {
			printf("NIE\n");
		}

		delete [] so;
	}
	return 0;
}