Colorful Square

Given $N$ points $P_1(x_1, y_1), P_2(x_2, y_2), \ldots, P_N(x_N, y_N)$ on a plane, each point has one of $K$ colors. The color of each point is an integer in $\{1, 2, \ldots, K\}$.

A square is called a colorful square if, for each of the $K$ colors, it contains at least one point of that color. Find the colorful square with the smallest side length and print that side length.

Here, squares must have all four sides horizontal or vertical. A point on the boundary of a square counts as inside it. A square with side length 0, which is a single point, also counts as a valid square.

The first line contains two integers $N$ and $K$, separated by a single space.

The next $N$ lines follow. The $i$-th line contains three integers $x_i$, $y_i$, and $k_i$, separated by single spaces. They describe the point $(x_i, y_i)$ and its color $k_i$.

Print the answer to the problem on the first line.

• $2 \le N \le 100\,000$
• $2 \le K \le N$
• For every $i$ ($1 \le i \le N$), $x_i$ and $y_i$ are integers from 1 to 250 000.
• For every color $k$ ($1 \le k \le K$), at least one of the $N$ points has color $k$.