408075: GYM102979 C Colorful Squares

There are $$$N$$$ points on a plane: $$$P_1$$$ $$$(x_1, y_1)$$$, $$$P_2$$$ $$$(x_2, y_2)$$$, ..., $$$P_N$$$ $$$(x_N, y_N)$$$. Each point has a color denoted by an integer from $$$1$$$ to $$$K$$$.

Consider a square with edges parallel to coordinate axes. The square is colorful if it contains points of all $$$K$$$ colors inside or on its border. It is allowed for the square to have edge length $$$0$$$, thus covering just a single point.

Find a colorful square with the minimum side length, and print that length.

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$2 \le N \le 10^5$$$, $$$2 \le K \le N$$$).

Then $$$N$$$ lines follow. The $$$i$$$-th of these lines contains three integers, $$$x_i$$$, $$$y_i$$$, and $$$c_i$$$: the coordinates of the $$$i$$$-th point and its color, respectively ($$$1 \le x_i, y_i \le 2.5 \cdot 10^5$$$, $$$1 \le c_i \le K$$$). You may assume that there is at least one point for each of $$$k$$$ colors.

Print one integer: the answer to the problem.

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

1

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

5

4 2
1 1 1
1 1 1
1 1 2
1 1 2

0