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
#include <cstdio>
#include <cstdlib>
#include <map>
#include <tuple>
#include <algorithm>

typedef long long i64;

const int N = 2000 + 10;
const i64 INF = 0x3f3f3f3f3f3f3f3fLL;

int n, ans[N];

struct Info {
  i64 x, y;
  int z;
  Info() {}
  Info(i64 _x, i64 _y, int _z): x(_x), y(_y), z(_z) {}
  inline bool operator< (const Info &rhs) const {
    return std::tie(x, y) < std::tie(rhs.x, rhs.y);
  }
} a[N];

i64 b[N];

bool print(i64 h, i64 w) {
  for (int i = 1; i <= n; ++i) if (!(ans[i] && ans[i] <= 2000000000)) return false;
  i64 area = h * w;
  for (int i = 1; i <= n; ++i) if ((area -= ans[i] * ans[i]) < 0) return false;
  if (area) return false;
  static int pos[N];
  for (int i = 1; i <= n; ++i) pos[a[i].z] = i;
  printf("TAK");
  for (int i = 1; i <= n; ++i) printf(" %d", ans[pos[i]]);
  putchar('\n');
  return true;
}

i64 solve(i64 h) {
  i64 res = 0;
  std::map<i64, i64> pool;
  for (int i = 1; i <= n; ++i) {
    i64 cur = std::min(h - a[i].y, b[i]);
    if (cur < 0) return 0;
    auto it = pool.upper_bound(a[i].y);
    while (it != pool.end() && it->second <= a[i].x) pool.erase(it++);
    if (it != pool.end()) cur = std::min(cur, it->first - a[i].y);
    pool[a[i].y] = std::max(pool[a[i].y], a[i].x + cur);
    res = std::max(res, a[i].x + (ans[i] = cur));
  }
  return res;
}

int main() {
  int tcase;
  for (scanf("%d", &tcase); tcase--;) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].x, &a[i].y), a[i].z = i;
    if (n == 1) {
      puts("TAK 1");
      continue;
    }
    std::sort(a + 1, a + n + 1);
    for (int i = n; i > 0; --i) a[i].x -= a[1].x;
    i64 t = a[1].y;
    for (int i = 2; i <= n; ++i) t = std::min(t, a[i].y);
    for (int i = 1; i <= n; ++i) a[i].y -= t;
    for (int i = 1; i <= n; ++i) {
      b[i] = INF;
      for (int j = n; j > i; --j) if (a[j].y >= a[i].y) b[i] = std::min(b[i], std::max(a[j].x - a[i].x, a[j].y - a[i].y));
    }
    int m = 1;
    while (m < n && a[m + 1].x == a[1].x) ++m;
    for (int i = 1; i <= n; ++i) {
      if (i > 1 && a[i].x == a[i - 1].x) continue;
      i64 h = a[m].y + llabs(a[m].x - a[i].x), w = solve(h);
      if (h == a[m].y) ans[m] = w, h += w;
      if (print(h, w)) goto success;
    }
    puts("NIE");
 success:
    continue;
  }
  return 0;
}