T574952 「PA Mashup #2」马赛克

给定二维平面上的 $n$ 个整点。第 $i$ 个点的坐标是 $(x_i,y_i)$。 构造 $n$ 个正方形，其中第 $i$ 个正方形的左下角顶点是 $(x_i,y_i)$，满足以下条件： - 这 $n$ 个正方形的并是一个矩形； - 任取 $1\le i\lt j\le n$，正方形 $i,j$ 的交面积为 $0$。（也就是说，正方形的边缘可以重合，但正方形不能相交。） 这里的「并」指的是连续意义上的并。用不太恰当的结构化学术语，就是这些正方形「无隙并置」成矩形。

**本题单个测试点内有多组测试数据。** 第一行，正整数 $T$，表示测试数据组数。接下来依次描述 $T$ 组测试数据。 每组测试数据中，第一行一个正整数 $n$。 接下来 $n$ 行，每行两个非负整数 $x_i,y_i$。

对于每组测试数据输出一行： 如果不可能，输出一行一个 $\texttt{NIE}$。 否则输出 $\texttt{TAK}$ $l_1$ $l_2$ $\ldots$ $l_n$，其中正整数 $l_i$ 表示正方形 $i$ 的边长。 你需要保证 $1\le l_i\le 2\times 10^9$。保证如果存在解，则存在一组 $1\le l_i\le 2\times 10^9$ 的合法解。

样例二、三是无私馈赠。后面忘了。 - $1\le T\le 50$； - $1\le n\le 2\times 10^3$，$1\le \sum n\le 5\times 10^3$； - $0\le x_i,y_i\le 10^9$； - 如果存在解，则存在 $1\le l_i\le 2\times 10^9$ 的合法解。