Description

PUBG 是一款多人在线大逃杀视频游戏。在游戏中，最多一百名玩家跳伞到一个岛上，搜寻武器和装备以击杀其他玩家，同时避免自己被击杀。空投是游戏中的一个关键元素，因为空投通常携带强大的武器或大量补给，帮助玩家生存。

考虑游戏的战场是一个二维平面。一个空投刚刚降落在点 $(x_0, y_0)$（$x_0$ 和 $y_0$ 都是整数），战场上的所有 $n$ 名玩家，其中 $(x_i, y_i)$（$x_i$ 和 $y_i$ 都是整数）表示第 $i$ 名玩家的初始位置，开始以以下模式向空投移动：

• 如果一个活着的玩家在这个时间单位开始时的位置不等于 $(x_0, y_0)$，他将开始他的下一步移动。
• • 假设他当前在点 $(x, y)$。对于他的下一步移动，他将考虑四个点 $(x, y - 1)$、$(x, y + 1)$、$(x - 1, y)$ 和 $(x + 1, y)$。
• • 他将选择其中一个到空投 $(x_0, y_0)$ 的曼哈顿距离最小的点作为他下一步的目的地。回忆一下，两点 $(x_a, y_a)$ 和 $(x_b, y_b)$ 之间的曼哈顿距离定义为 $|x_a - x_b| + |y_a - y_b|$。
• • 如果两个或更多点到空投的曼哈顿距离相同，他将使用以下优先级规则来打破平局：$(x, y - 1)$ 优先级最高，$(x, y + 1)$ 优先级第二，$(x - 1, y)$ 优先级第三，$(x + 1, y)$ 优先级最低。
• • 在这个时间单位结束时，他到达他的目的地。
• 如果一个活着的玩家在这个时间单位开始时的位置等于 $(x_0, y_0)$，他将继续用空投中的补给填满他的背包，并停留在 $(x_0, y_0)$。

但战斗很激烈，几乎不可能所有玩家都安全到达空投。如果两个或更多玩家在点 $(x', y')$ 相遇，且 $(x', y')$ 不是 $(x_0, y_0)$，他们将互相搏斗并全部阵亡，没有人存活。

BaoBao 是该游戏的忠实粉丝，对成功到达空投位置的玩家数量感兴趣，但他不知道 $x_0$ 的值。给定 $y_0$ 的值和每个玩家的初始位置，请帮助 BaoBao 计算对于所有 $x_0 \in \mathbb{Z}$（$\mathbb{Z}$ 是所有整数的集合，注意 $x_0$ 可以是正数、零或负数），成功到达空投位置的玩家数量的最小值和最大值。

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $y_0$（$1 \le n \le 10^5$，$1 \le y_0 \le 10^5$），表示玩家的数量和空投的 $y$ 值。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le 10^5$），表示第 $i$ 名玩家的初始位置。

保证所有测试用例中 $n$ 的总和不超过 $10^6$，并且在每个测试用例中没有两个玩家共享相同的初始位置。

Output Format

对于每个测试用例输出一行，包含两个整数 $p_\text{min}$ 和 $p_\text{max}$，用一个空格分隔。$p_\text{min}$ 表示成功到达空投位置的玩家数量的最小可能值，而 $p_\text{max}$ 表示最大可能值。

3
3 2
1 2
2 1
3 5
3 3
2 1
2 5
4 3
2 3
1 3
4 3

1 3
0 3
2 2

Hint

我们现在解释第一个样例测试用例。

为了得到 $p_\text{min} = 1$ 的答案，应该考虑 $x_0 = 3$。下表显示了当 $x_0 = 3$ 时每个玩家在每个时间单位结束时的位置。

为了得到 $p_\text{max} = 3$ 的答案，应该考虑 $x_0 = 2$。下表显示了当 $x_0 = 2$ 时每个玩家在每个时间单位结束时的位置。

题面翻译由 ChatGPT-4o 提供。