CF1619G.Unusual Minesweeper

Polycarp is very fond of playing the game Minesweeper. Recently he found a similar game and there are such rules.

There are mines on the field, for each the coordinates of its location are known ($x_i, y_i$). Each mine has a lifetime in seconds, after which it will explode. After the explosion, the mine also detonates all mines vertically and horizontally at a distance of $k$ (two perpendicular lines). As a result, we get an explosion on the field in the form of a "plus" symbol ('+'). Thus, one explosion can cause new explosions, and so on.

Also, Polycarp can detonate anyone mine every second, starting from zero seconds. After that, a chain reaction of explosions also takes place. Mines explode instantly and also instantly detonate other mines according to the rules described above.

Polycarp wants to set a new record and asks you to help him calculate in what minimum number of seconds all mines can be detonated.

波利卡普非常喜爱玩扫雷游戏。最近，他发现了一款类似的游戏，其规则如下：

游戏场地中分布着若干颗地雷，每颗地雷的位置坐标 $(x_i, y_i)$ 已知。每颗地雷具有一个以秒为单位的寿命，到期后将自动爆炸。爆炸发生后，该地雷还会在水平和垂直方向上、距离不超过 $k$ 的范围内引爆所有其他地雷（即沿两条互相垂直的直线）。因此，一次爆炸会在场地上形成一个“加号”（'+'）形状的爆炸区域。于是，一次爆炸可能引发新的爆炸，如此连锁进行。

此外，波利卡普可以从第 0 秒起，每秒手动引爆任意一颗尚未爆炸的地雷。随后，同样会按照上述规则触发连锁爆炸。所有爆炸均瞬时发生，且引爆其他地雷的过程也是瞬时完成的。

波利卡普希望打破纪录，因此请你帮助他计算：引爆所有地雷所需的最短时间（以秒为单位）。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

An empty line is written in front of each test suite.

Next comes a line that contains integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$) — the number of mines and the distance that hit by mines during the explosion, respectively.

Then $n$ lines follow, the $i$-th of which describes the $x$ and $y$ coordinates of the $i$-th mine and the time until its explosion ($-10^9 \le x, y \le 10^9$, $0 \le timer \le 10^9$). It is guaranteed that all mines have different coordinates.

It is guaranteed that the sum of the values $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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 \text{timer} \le 10^9$）。保证所有地雷的坐标互不相同。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

Print $t$ lines, each of the lines must contain the answer to the corresponding set of input data — the minimum number of seconds it takes to explode all the mines.

输出 $t$ 行，每行必须包含对应输入数据的答案——即引爆所有地雷所需的最少秒数。

Picture from examples

First example:

• $0$ second: we explode a mine at the cell $(2, 2)$, it does not detonate any other mine since $k=0$.
• $1$ second: we explode the mine at the cell $(0, 1)$, and the mine at the cell $(0, 0)$ explodes itself.
• $2$ second: we explode the mine at the cell $(1, 1)$, and the mine at the cell $(1, 0)$ explodes itself.

Second example:

• $0$ second: we explode a mine at the cell $(2, 2)$ we get:

• $1$ second: the mine at coordinate $(0, 0)$ explodes and since $k=2$ the explosion detonates mines at the cells $(0, 1)$ and $(1, 0)$, and their explosions detonate the mine at the cell $(1, 1)$ and there are no mines left on the field.

示例中的图片

第一个示例：

• 第 $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)$ 处的地雷，此时场地上已无剩余地雷。