波利卡普非常喜欢玩扫雷游戏。最近他发现了一个类似的游戏,还有这样的规则。
场地上有地雷,每个地雷的位置坐标都是已知的($$$x_i, y_i$$$)。每个地雷都有几秒钟的寿命,之后就会爆炸。爆炸后,地雷还会引爆距离$$$k$$$(两条垂直线)垂直和水平方向上的所有地雷。结果,我们在场上看到了“加号”符号(“+”)形式的爆炸。因此,一次爆炸可能会引起新的爆炸,依此类推。
此外,波利卡普每秒都可以引爆任何人的地雷,从零秒开始。之后,还会发生爆炸的连锁反应。根据上述规则,地雷立即爆炸,并立即引爆其他地雷。
波利卡普想要创造新的记录,请你帮他计算最少需要多少秒才能引爆所有地雷。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。
每个测试套件前面都写有一个空行。
接下来是一行,包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$) — 分别是地雷数量和爆炸期间被地雷击中的距离。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 行描述了第 $$$i$$$ 地雷的 $$$x$$$ 和 $$$y$$$ 坐标以及爆炸之前的时间 ($$$-10^9 \le x, y \le 10^9$$$, $$$0 \le timer \le 10^9$$$)。保证所有地雷都有不同的坐标。
保证测试中所有测试用例的值 $$$n$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
打印 $$$t$$$ 行,每行必须包含相应输入数据集的答案 - 引爆所有地雷所需的最少秒数。
示例
输入 #1
3 5 0 0 0 1 0 1 4 1 0 2 1 1 3 2 2 9 5 2 0 0 1 0 1 4 1 0 2 1 1 3 2 2 9 6 1 1 -1 3 0 -1 9 0 1 7 -1 0 1 -1 1 9 -1 -1 7
输出 #1
2 1 0
注意
示例图片
第一个例子:
- $$$0$$$ 第二:我们在 $$$(2, 2)$$$ 单元格引爆了一个地雷,因为 $$$k=0$$$,它不会引爆任何其他地雷。
- $$$1$$$ 第二:我们引爆单元格 $$$(0, 1)$$$ 处的地雷,单元格 $$$(0, 0)$$$ 处的地雷会自行爆炸。
- $$$2$$$ 第二:我们引爆炸了单元格 $$$(1, 1)$$$ 处的地雷,单元格 $$$(1, 0)$$$ 处的地雷自行爆炸。
第二个例子:
- $$$0$$$ 第二:我们在 $$$(2, 2)$$$ 单元格引爆地雷,我们得到:
- $$$1$$$ 第二个:坐标 $$$(0, 0)$$$ 处的地雷爆炸,由于 $$$k=2$$$,爆炸引爆了单元格 $$$(0, 1)$$$ 和 $$$(1, 0)$$$ 处的地雷,它们的爆炸引爆了单元格 $$$(1, 1)$$$ 处的地雷,并且没有留下任何地雷在球场上。