由于一次不幸的巧合（以及学生管理系统中某个恶意 Bug 的影响），Bajtazar 今年的学生实习是在考古实验室进行的。他目前正试图修复一幅古老的马赛克拼图，但这幅拼图留存下来的部分非常少——已知它原本是一个矩形，被分割成了 $n$ 个大小可能各不相同的正方形瓷砖。遗憾的是，矩形的尺寸和各个正方形的边长均已不可考。从历史资料中唯一能推断出的信息是这些瓷砖左下角的位置。

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

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

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 50$)，表示测试数据的组数。接下来是 $t$ 组测试数据的描述：

每组数据的第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示点数。 接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$)，表示第 $i$ 个点的坐标。 同一组数据中，任意两个点互不重合。

所有测试数据中点的总数不超过 $5000$。

输出格式

对于每组测试数据，输出一行。如果不存在满足条件的方案，输出 NIE。否则，输出 TAK，并在其后输出 $n$ 个正整数，用空格隔开；第 $i$ 个数表示方案中第 $i$ 个正方形的边长。该数值不应超过 $2 \cdot 10^9$。你可以假设，如果测试数据有解，则一定存在一个解，其中每个正方形的边长不超过 $2 \cdot 10^9$。

如果存在多个解，输出其中任意一个即可。

样例

输入 1

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

输出 1

TAK 1 1
NIE
TAK 1 1 3 2