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
#include <bits/stdc++.h>

using namespace std;

typedef unsigned int ui;
typedef unsigned long long llu;
typedef pair<ui, ui> ii;
typedef pair<ui, ii> iii;

#define X first
#define Y second

const ui inf = 2000000009;

bool comp(const iii &a, const iii &b) {
    if(a.Y.X != b.Y.X)
        return a.Y.X < b.Y.X;
    return a.Y.Y > b.Y.Y;
}

int t, n;
iii P[2007];
ui res[2007];
set<ii> S;
set<iii> S2;

bool check(ui a, int first = 0) {
    llu area = 0;

    S.clear();
    S2.clear();
    S.insert({P[first].Y.Y + a, P[first].Y.Y + a + 1});
    int i = 0;
    ui xmin = inf, ymin = inf, xmax = 0, ymax = 0;
    for(i = first ; i < n ; i++) {
        auto p = P[i].Y;
        while(S2.size() > 0 && (*S2.begin()).X <= p.X) {
            auto it = S2.begin();
            S.erase((*it).Y);
            S2.erase(it);
        }

        auto it = S.upper_bound({p.Y, inf});
        if(it != S.begin()) {
            auto it2 = prev(it);
            if((*it2).X <= p.Y && p.Y < (*it2).Y)
                return false;
        }

        ui b = (*it).X - p.Y;
        res[P[i].X] = b;
        area += llu(b) * llu(b);

        xmin = min(xmin, p.X);
        xmax = max(xmax, p.X + b);
        ymin = min(ymin, p.Y);
        ymax = max(ymax, p.Y + b);

        S.insert({p.Y, p.Y + b});
        S2.insert({p.X + b, {p.Y, p.Y + b}});
    }

    if((llu(xmax) - llu(xmin)) * (llu(ymax) - llu(ymin)) != area)
        return false;
    if(first == 1) {
        if(xmin != P[0].Y.X)
            return false;
        res[P[0].X] = xmax - xmin;
    }

    printf("TAK");
    for(int i = 0 ; i < n ; i++)
        printf(" %u", res[i]);
    printf("\n");
    return true;
}

int main() {
    scanf("%d", &t);

    while(t--) {
        scanf("%d", &n);
        for(int i = 0 ; i < n ; i++) {
            scanf("%u %u", &P[i].Y.X, &P[i].Y.Y);
            P[i].X = i;
        }

        if(n == 1) {
            printf("TAK 1\n");
            continue;
        }

        sort(P, P + n, comp);

        bool ok = false;
        for(int i = 1 ; i < n ; i++) {
            if(P[i].Y.X > P[0].Y.X && check(P[i].Y.X - P[0].Y.X)) {
                ok = true;
                break;
            }
            if(P[i].Y.Y >= P[0].Y.Y)
                break;
        }

        if(ok) continue;

        if(P[0].Y.Y > P[1].Y.Y && check(P[0].Y.Y - P[1].Y.Y, 1))
            continue;

        printf("NIE\n");
    }

    return 0;
}