Unusual Minesweeper
Contest: Codeforces Round 762 (Div. 3)
Difficulty rating: 2000
Tags: binary search, dfs and similar, dsu, greedy, sortings

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
2
1
0

Editorial:
Our first task is to separate mines into components. We will store in the hashmap $$$mapx$$$ at the $$$x$$$ coordinate all the $$$y$$$ coordinates where there is a mine. Let's do the same with the $$$mapy$$$ hashmap. Thus, going through the available arrays in $$$mapx$$$ and $$$mapy$$$, we connect adjacent elements into one component, if $$$|mapx[x][i] - mapx[x][i + 1]| <= k$$$, also with $$$mapy$$$.
As a result, we have components, where if you detonate one mine in the $$$j$$$'s component, then all the mines belonging to this component will also explode.
Further, we find a mine with a minimum timer in each component. Finding the minimum for each component, we store it conditionally in the array $$$a$$$. Now we know at what minimum time some component will explode if it is left unaffected.
To answer, it remains to find in the sorted array $$$a$$$ such a minimum index $$$i$$$ $$$(0 \le i \le a.size - 1)$$$ that $$$max (a[i], a.size - i - 2)$$$ is min.
And the general asymptotic behavior is $$$O(n log (n))$$$.