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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int N=2005;
const unsigned long long INF=1e18;
int n, t;
typedef unsigned long long ull;
ull ans[N], ans2[N];
struct Point
{
        ull x, y;
        int id;
};
Point tab[N];
bool cmp(Point x, Point y)
{
        if(x.y==y.y) return x.x<y.x;
        return x.y<y.y;
}
int main()
{
        scanf("%d", &t);
        while(t--)
        {
                ull pole=0, maksx=0, maksy=0, miny=INF, minx=INF;
                scanf("%d", &n);
                if(n==1)
                {
                        printf("TAK 1\n");
                        continue;
                }
                for(int i=1;i<=n;i++)
                {
                        scanf("%lld%lld", &tab[i].x, &tab[i].y);
                        tab[i].id=i;
                        ans[i]=INF;
                }
                sort(tab+1,tab+n+1,cmp);
                for(int i=1;i<=n;i++)
                {
                        if(tab[i].y!=tab[i+1].y && i!=n)
                        {
                                ans[i]=tab[i+1].y-tab[i].y;
                                maksy=max(maksy,tab[i].y+ans[i]);
                                maksx=max(maksx,tab[i].x+ans[i]);
                                continue;
                        }
                        ull ex=tab[i].x, ey=tab[i].y;
                        for(int j=1;j<=n;j++)
                        if(i!=j)
                        {
                                ull an=ans[j];
                                if(an==INF) an=0;
                                ull fx=tab[j].x, fy=tab[j].y;
                                if(fx>=ex && fy>=ey)
                                ans[i]=min(ans[i],max(fx-ex,fy-ey));
                                else
                                {
                                        if(fx>=ex && fy+an>ey)
   ans[i]=min(ans[i],fx-ex);
                                        if(fy>=ey && fx+an>ex)
                                        ans[i]=min(ans[i],fy-ey);
                                }
                        }
                        if(ans[i]==INF)
                        {
                                if(maksy>tab[i].y) ans[i]=maksy-tab[i].y;
                                else ans[i]=maksx-tab[i].x;
                        }
                        maksy=max(maksy,tab[i].y+ans[i]);
                        maksx=max(maksx,tab[i].x+ans[i]);
                }
                for(int i=1;i<=n;i++)
                {
                        minx=min(minx,tab[i].x);
                        miny=min(miny,tab[i].y);
                        maksy=max(maksy,tab[i].y+ans[i]);
                        maksx=max(maksx,tab[i].x+ans[i]);
                        pole+=ans[i]*ans[i];
                }
                bool czy=1;
                for(int i=1;i<=n;i++) if(ans[i]<=0) czy=0;
                if(pole!=(maksx-minx)*(maksy-miny) || !czy) printf("NIE");
                else
                {
                        printf("TAK ");
                        for(int i=1;i<=n;i++) ans2[tab[i].id]=ans[i];
                        for(int i=1;i<=n;i++) printf("%lld ", ans2[i]);
                }
                printf("\n");
        }
        return 0;
}