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
#include <bits/stdc++.h>
#define rep(a,b) for(int a = 0; a < b; a++)

using namespace std;
typedef long long ll;

struct point{
    ll x, y;
    int id;
    ll bok;
};

ll distX(point &a, point &b){
    return abs(a.x - b.x);
}

ll distY(point &a, point &b){
    return abs(a.y - b.y);
}

bool srt(point a, point b){
    return ((a.x + a.y) == (b.x + b.y) ? a.x > b.x : (a.x + a.y) < (b.x + b.y));
}

bool srt2(point a, point b){
    return a.id < b.id;
}

bool srt3(point a, point b){
    return a.x < b.x;
}

/*
10
0 0
0 1
0 2
0 3
1 0
1 2
3 0
3 1
3 2
3 3

*/

int main(){
    ios_base::sync_with_stdio(0);
    int t;
    cin >> t;

    int n;
    vector<point> v1;
    vector<point> pom;

    while(t--){
        bool odp = true;

        cin >> n;
        v1.clear();
        v1.resize(n);
        pom.clear();

        ll prX = 2e9, prY = 2e9, prW = 0, prH = 0, sW = 0, sH = 0;

        rep(i, n){
            cin >> v1[i].x >> v1[i].y;

            prX = min(v1[i].x, prX);
            prY = min(v1[i].y, prY);

            v1[i].id  = i;
            v1[i].bok = 2e9;
        }

        sort(v1.begin(), v1.end(), srt);

        for(int i = 0; i < v1.size(); i++){
            for(int j = i+1; j < v1.size(); j++){
                if(v1[j].y < v1[i].y || v1[j].x < v1[i].x) continue;
                v1[i].bok = min(v1[i].bok, max(distX(v1[i], v1[j]), distY(v1[i], v1[j])));
                if(i - 1 >= 0 && v1[i-1].x + v1[i-1].y == v1[i].x + v1[i].y) v1[i].bok = min(v1[i].bok, v1[i-1].x - v1[i].x);
            }

            if(v1[i].bok == 2e9){ pom.push_back(v1[i]); continue;}

            prW = max(prW, v1[i].x + v1[i].bok);
            prH = max(prH, v1[i].y + v1[i].bok);
            if(v1[i].x >= sW + prX) sW += v1[i].bok;
            if(v1[i].y >= sH + prY) sH += v1[i].bok;

            //cout << v1[i].id << ": " << v1[i].bok << endl;
        }
//cout << sW << " " << prW - prX << " " << sH << " " << prH - prY << endl;
        sort(v1.begin(), v1.end(), srt3);
        sort(pom.begin(), pom.end(), srt3);

        for(int i = 0; i <  pom.size(); i++){

          //  cout <<"!" << endl;
            if(pom[i].x == prW && pom[i].y == prY){
                pom[i].bok = min(prH - prY - (prY - pom[i].y), (i+1 < pom.size() ? pom[i+1].x - pom[i].x : (ll)2e9));
            }
            else if(pom[i].y == prH && pom[i].x == prX){
                pom[i].bok = min(prW - prX - (prX - pom[i].x), (i+1 < pom.size() ? pom[i+1].x - pom[i].x : (ll)2e9));
            }
            else if(pom[i].x < prW && pom[i].y < prH){
                if(prW - pom[i].x != prH - pom[i].y && i == pom.size()-1) odp = false;
                else{
                    pom[i].bok = min(prH - pom[i].y, (i+1 < pom.size() ? pom[i+1].x - pom[i].x : (ll)2e9));
                }
            }
            else { odp = false; break; }

            prW = max(prW, pom[i].x + pom[i].bok);
            prH = max(prH, pom[i].y + pom[i].bok);
            if(pom[i].x >= sW + prX) sW += pom[i].bok;
            if(pom[i].y >= sH + prY) sH += pom[i].bok;

          //  cout << pom[i].id << ": " << pom[i].bok << endl;
        }
        int start = 0;
        rep(i, v1.size()){
            if(v1[i].bok == 2e9) v1[i] = pom[start++];
        }


        if(sW != prW - prX || sH != prH - prY) odp = false;

        if(odp){
            cout << "TAK ";
            sort(v1.begin(), v1.end(), srt2);
            rep(i, v1.size()) cout << v1[i].bok << " ";
            cout << endl;
        }
        else cout << "NIE\n";

    }
}