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$。（也就是说，正方形的边缘可以重合，但正方形不能相交。） 这里的「并」指的是连续意义上的并。用不太恰当的结构化学术语，就是这些正方形「无隙并置」成矩形。

无

无

样例二、三是无私馈赠。后面忘了。 - $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$ 的合法解。