#P11806. [PA 2017] 马赛克

[PA 2017] 马赛克

题目背景

译自 PA 2017 R3T1。

题目描述

给定二维平面上的 nn 个整点。第 ii 个点的坐标是 (xi,yi)(x_i,y_i)

构造 nn 个正方形,其中第 ii 个正方形的左下角顶点是 (xi,yi)(x_i,y_i),满足以下条件:

  • nn 个正方形的并是一个矩形;
  • 任取 1i<jn1\le i\lt j\le n,正方形 i,ji,j 的交面积为 00。(也就是说,正方形的边缘可以重合,但正方形不能相交。)

输入格式

本题单个测试点内有多组测试数据。

第一行,正整数 TT,表示测试数据组数。接下来依次描述 TT 组测试数据。

每组测试数据中,第一行一个正整数 nn

接下来 nn 行,每行两个非负整数 xi,yix_i,y_i

输出格式

对于每组测试数据输出一行:

如果不可能,输出一行一个 NIE\texttt{NIE}

否则输出 TAK\texttt{TAK} l1l_1 l2l_2 \ldots lnl_n,其中正整数 lil_i 表示正方形 ii 的边长。

你需要保证 1li2×1091\le l_i\le 2\times 10^9。保证如果存在解,则存在一组 1li2×1091\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

提示

  • 1T501\le T\le 50
  • 1n2×1031\le n\le 2\times 10^31n5×1031\le \sum n\le 5\times 10^3
  • 0xi,yi1090\le x_i,y_i\le 10^9
  • 如果存在解,则存在 1li2×1091\le l_i\le 2\times 10^9 的合法解。