题目描述

题目译自 PA 2017 Runda 3 Mozaika

由于一系列不幸的巧合（以及某个恶意 bug 存在于学业管理系统中），Bajtazar 今年在考古实验室进行学生实习。他目前正在尝试重建一块古老的马赛克，这块马赛克保存下来的信息非常少——只知道它原本是一个矩形，被分成 $n$ 个可能大小不同的正方形瓷砖。然而，矩形的尺寸和各正方形的边长都已无从得知。从历史资料中唯一能推断出的信息是各瓷砖左下角的位置。

事实证明，即使是考古学家有时也需要程序员的帮助！给定 $n$ 个点在平面上的位置（即各瓷砖的左下角坐标），请找到 $n$ 个边平行于坐标轴的正方形，使得：

• 所有正方形组合成一个矩形；
• 任意两个正方形的内部没有公共点；
• 第 $i$ 个正方形的左下角与给定的第 $i$ 个点重合。

输入格式

输入数据的第一行包含一个整数 $t$ $(1 \leq t \leq 50)$，表示输入中的测试用例数量。接下来是 $t$ 个测试用例的描述，格式如下：

每个测试用例的第一行包含一个整数 $n$ $(1 \leq n \leq 2000)$，表示该用例中的点数量。

接下来的 $n$ 行每行包含两个整数 $x_{i}, y_{i}$ $(0 \leq x_{i}, y_{i} \leq 10^{9})$，表示第 $i$ 个点的坐标。同一测试用例中的任意两点不重合。

所有测试用例中点的总数量不超过 $5000$。

输出格式

对于输入中的每个 $t$ 个测试用例，输出一行。如果给定用例无法找到合适的正方形排列，则输出 NIE。否则，输出 TAK，后面跟着 $n$ 个用单个空格分隔的正整数；第 $i$ 个数字表示合法方案中第 $i$ 个正方形的边长。边长不应超过 $2 \cdot 10^{9}$。保证如果测试用例存在合法方案，则一定存在一个每个正方形边长不超过 $2 \cdot 10^{9}$ 的合法方案。

如果存在多个合法方案，输出其中任意一个即可。

3
2
0 0
0 1
2
3 2
2 3
4
1 1
2 1
3 1
1 2

TAK 1 1
NIE
TAK 1 1 3 2