配点 : 100 点
問題文
有一个无限广阔的二维格子。
在格子上有 N 个人,i 第 n 个人起初在 (R_{i} ,C_{i}) 每个人戴着金色或银色其中一种颜色的帽子。 i 第 n 个人在 H_i = G 时是金色,H_i = S 的时候戴着银色帽子。
1 每回合,各人可以根据帽子的颜色,从当前位置进行如下移动。
- 戴金色帽子的人:
可以停留在该格子,或者按照将棋中的金的移动方式移动。严格来说,可以将当前位置的格子移动到 (i, j) 转至 (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j), (i, j+1), (i+1, j) 的任意一个。 - 戴银色帽子的人:
可以停留在该格子,或者按照将棋中的银的移动方式移动。严格来说,可以将当前位置的格子移动到 (i, j) 转至 (i-1, j-1), (i-1, j), (i-1, j+1), (i, j), (i+1, j-1), (i+1, j+1) 的任意一个。

N 请计算所有人聚集到同一格子所需的最少回合数。
T 会给出若干测试用例,请针对每个测试用例求出答案。
制約
- T, N, R_i, C_i 是一个整数
- 1 \le T \le 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le R_i \le 10^9
- 1 \le C_i \le 10^9
- H_i 是
您也可以写
G或S任何一个 - 1 覆盖输入中的所有测试用例。 N 的总和是 2 \times 10^5 以下
部分点
附加限制
如果正确答案是满足 H_i = G 的数据集
给出 30 点。
如果您正确回答了所有满足
入力
输入按以下格式给出。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里,\mathrm{case}_i 是 您也可以写 i 个测试用例。每个测试用例均按以下格式给出。
N R_1 C_1 H_1 R_2 C_2 H_2 \vdots R_N C_N H_N
出力
T 测试用例的答案,并用换行符分隔。 例如,通过按如下方式移动
入力例 1
5 2 2 1 G 4 4 S 3 2 1 G 2 4 G 2 2 S 2 3 2 G 3 2 S 1 3 4 G 10 2 4 S 2 3 G 10 8 S 7 3 S 2 6 S 7 1 S 9 1 G 5 2 S 7 8 G 2 1 S
出力例 1
2 2 0 0 5
1 测试用例,2 你们可以轮流聚集在同一个方格中。
- 1 转
对
- 人 1 是 您也可以写 (2, 2) 移至
- 人 2 是 您也可以写 (3, 3) 移至
- 2 转
对
- 人 1 留在原地
- 人 2 是 您也可以写 (2, 2) 移至
2 测试用例,2 你们可以轮流聚集在同一个方格中。
- 1 转
对
- 人 1 是 您也可以写 (1, 2) 移至
- 人 2 是 您也可以写 (1, 3) 移至
- 人 3 是 您也可以写 (1, 2) 移至
- 2 转
对
- 人 1 留在原地
- 人 2 是 您也可以写 (1, 2) 移至
- 人 3 留在原地
3 对于测试用例,大家从一开始就聚集在同一个广场上。
入力例 2
2 2 1 1 G 3 3 G 5 1 4 G 5 2 G 3 1 G 3 6 G 1 2 G
出力例 2
2 3
1 测试用例,2 你们可以轮流聚集在同一个方格中。
- 1 转
对
- 人 1 是 您也可以写 (2, 1) 移至
- 人 2 是 您也可以写 (2, 2) 移至
- 2 转
对
- 人 1 留在原地
- 人 2 是 您也可以写 (2, 1) 移至
这个输入示例满足部分分数的否定条件。