화려한 정사각형

평면에 $N$개의 점 $P_1(x_1, y_1), P_2(x_2, y_2), \ldots, P_N(x_N, y_N)$이 주어진다. 각 점은 $K$개의 색깔 중 하나를 갖고, 색깔은 $\{1, 2, \ldots, K\}$의 정수로 표현된다.

어떤 정사각형이 $K$개의 색깔 각각에 대해 그 색깔의 점을 하나 이상 포함하면, 이 정사각형을 화려한 정사각형이라고 부른다. 변의 길이가 가장 작은 화려한 정사각형을 찾아서 그 변의 길이를 출력하라.

여기서 정사각형은 네 변이 모두 수평 또는 수직인 정사각형만 가리킨다. 정사각형의 내부뿐 아니라 경계에 놓인 점도 정사각형에 포함된다. 한 변의 길이가 0이어서 점으로 나타나는 정사각형도 하나의 경우로 본다.

첫 번째 줄에 두 정수 $N$과 $K$가 공백 하나로 구분되어 주어진다.

이후 $N$개의 줄이 주어진다. $i$번째 줄에는 세 정수 $x_i$, $y_i$, $k_i$가 공백 하나로 구분되어 주어지며, 이는 점 $(x_i, y_i)$와 그 점의 색깔 $k_i$를 뜻한다.

첫 번째 줄에 문제의 정답을 출력한다.

• $2 \le N \le 100\,000$
• $2 \le K \le N$
• 모든 $i$ ($1 \le i \le N$)에 대해, $x_i$와 $y_i$는 1 이상 250 000 이하의 정수이다.
• 모든 색 $k$ ($1 \le k \le K$)에 대해, $N$개의 점 중 색깔이 $k$인 점이 최소 하나 존재한다.