Alice 想要拜访 Bob。然而，他们居住在一个多丘陵的地带，而 Alice 不喜欢在丘陵中行走。她有一张该地区的地图，上面标有等高线。你需要计算在使这些数值最小化的路线中，累计爬升的高度和累计下降的高度。为了达到这个目的，她需要走多远并不重要。

由于你不知道等高线之间的地形具体是什么样子的，你无法确切知道她在实际中会爬升和下降多少，但你应该根据能从地图中推导出的信息，计算在最理想情况下可能达到的最小值。

地图表示为一个 $xy$ 网格。Alice 住在 $(0, 0)$，Bob 住在 $(100\,000, 0)$。等高线用多边形表示，多边形不能自交，也不能与其他多边形相交。此外，Alice 和 Bob 都不恰好住在等高线上。

来自样例输入的第二个测试用例（压缩图）。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。接下来是每个测试用例的数据：

• 一行包含一个整数 $0 \le N \le 2\,500$，表示等高线的数量。
• 每个等高线占一行，包含：等高线的高度 $1 \le H_i \le 1\,000$，多边形的顶点数 $3 \le P_i \le 2\,000$，以及顶点的坐标 $x_1, y_1, \dots, x_{P_i}, y_{P_i}$，其值为整数且满足 $-300\,000 \le x_i, y_i \le 300\,000$。

所有测试用例中的多边形顶点总数不超过 $200\,000$。

输出格式

对于每个测试用例：

• 输出一行，包含两个整数：累计爬升的高度和累计下降的高度。

样例

输入样例 1

2
2
20 3 10 10 0 -10 -10 10
25 3 20 20 0 -20 -20 20
3
100 4 -1 1 1 1 1 -1 -1 -1
300 8 -2 2 2 2 2 -2 5 -2 5 1 6 1 6 -3 -2 -3
50 8 3 3 100001 3 100001 -1 7 -1 7 2 4 2 4 -1 3 -1

输出样例 1

5 0
200 250