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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const unsigned INF = 0xfffffff;
template<typename T>
inline T read()
{
    T temp;
    cin>>temp;
    return temp;
}

template<typename T>
inline vector<T> readn(unsigned x)
{
    vector<T> temp(x);
    generate(temp.begin(), temp.end(), read<T>);
    return temp;
}

struct Corner
{
    unsigned edgel;
    pair<unsigned, unsigned> pos;
    unsigned defined;
};

struct CornToSort
{
    unsigned index;
    pair<unsigned, unsigned> pos;
    inline bool operator<(const CornToSort& ext)const
    {
        if(pos.second != ext.pos.second)
            return pos.second < ext.pos.second;
        return pos.first < ext.pos.first;
    }
};

int main()
{
    auto t = read<unsigned>();
    for(unsigned q = 0; q < t; ++q)
    {
        auto n = read<unsigned>();
        vector<Corner> corns(n);
        vector<CornToSort>sorx(n);
        unsigned minh = INF;
        unsigned mind = INF;
        for(unsigned i = 0; i < n; ++i)
        {
            pair<unsigned, unsigned> in = { read<unsigned>(), read<unsigned>() };
            corns[i].pos = in;
            corns[i].defined = 0;
            sorx[i].pos = in;
            sorx[i].index = i;
            minh = min(minh, sorx[i].pos.second);
            mind = min(mind, sorx[i].pos.first);
        }
        if(n == 1)
        {
            cout<<"TAK\n1\n";
            continue;
        }
        sort(sorx.begin(), sorx.end());
        unsigned border = INF;
        pair<unsigned,unsigned> undefined;
        unsigned maxh = 0;
        for(unsigned i = 0; i < n; ++i)
        {
            if(corns[sorx[i].index].defined == 2) continue;
            unsigned maks = border;
            for(unsigned j = 0; j < n; ++j)
            {
                if(i == j) continue;
                if(corns[sorx[j].index].defined == 0)
                {
                    if(sorx[j].pos.second == sorx[i].pos.second && sorx[j].pos.first > sorx[i].pos.first)
                        maks = min(maks,sorx[j].pos.first - sorx[i].pos.first);
                }
                if(corns[sorx[j].index].defined == 2)
                {
                    if(sorx[j].pos.first > sorx[i].pos.first && sorx[j].pos.second <= sorx[i].pos.second && sorx[j].pos.second + corns[sorx[j].index].edgel > sorx[i].pos.second)
                        maks = min(maks,sorx[j].pos.first - sorx[i].pos.first);
                }
                if(corns[sorx[j].index].defined == 1)
                {
                    if(sorx[i].pos.first + maks > undefined.first)
                    {
                        corns[sorx[undefined.second].index].defined = 2;
                        corns[sorx[undefined.second].index].edgel = sorx[i].pos.second - sorx[undefined.second].pos.second;
                        border = sorx[undefined.second].pos.first + corns[sorx[undefined.second].index].edgel;
                        maks = min(maks, border - sorx[i].pos.first);
                    }
                }
            }
            if(maks == INF)
            {
                corns[sorx[i].index].defined = 1;
                undefined.first = sorx[i].pos.first;
                undefined.second = i;
            }
            else
            {
                corns[sorx[i].index].edgel = maks;
                corns[sorx[i].index].defined = 2;
                maxh = max(maxh,sorx[i].pos.second + corns[sorx[i].index].edgel);
            }
        }
        ll rectp = ll(maxh - minh) * ll(border - mind);
        ll sump = 0;
        for(unsigned i = 0; i < n; ++i)
        {
            ll p = corns[i].edgel;
            sump += p * p;
        }
        if(rectp != sump)
        {
            cout<<"NIE\n";
            continue;
        }
        cout<<"TAK\n";
        for(unsigned i = 0; i < n; ++i)
        {
            cout<<corns[i].edgel<<" ";
        }
        cout<<"\n";
    }
    return 0;
}