由于一次不幸的巧合（以及大学系统中的一个恶意漏洞），Byton 在一家考古工作室实习。他试图重建一幅古代马赛克。他知道它最初的形状是一个被分割成 $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$。

输出格式

对于输入中的每个测试用例，打印一行。如果对于给定的集合，不存在正确的正方形瓷砖组合，则打印单词 NO。否则，打印 YES，随后打印 $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

YES 1 1
NO
YES 1 1 3 2