题目背景

译自 PA 2017 R3T1。

题目描述

给定二维平面上的 $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$ 的合法解。

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

提示

• $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$ 的合法解。