화려한 정사각형

평면에 $N$개의 점 $P1(x1, y1), P2(x2, y2$), . . . , PN(xN, yN)이 주어지며, 각각의 점들은 총 $K$개의 색깔 중 하나를 가지고 있다. 각 점의 색깔은 {1, 2, . . . , $K}$ 중의 한 정수로 표현된다.

어떤 정사각형이 각 $K$개의 색깔에 대해 해당 색깔의 점을 하나 이상 포함하고 있다면, 이 정사각형을 화 려한 정사각형이라고 부른다. 변의 길이를 최소로 하는 화려한 정사각형을 찾아서 그 변의 길이를 출력하는 프로그램을 작성하라.

단, 여기서 정사각형은 네 변이 모두 수평 혹은 수직인 것에 한정하며, 정사각형의 내부가 아닌 경계에 놓인 점들도 그 정사각형에 포함된다고 생각한다. 정사각형의 한 변의 길이가 0이 되어 점으로 나타나는 경우도 정사각형의 한 경우로 간주한다.

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

1. (3점) $N \le 50$, 모든 $i (1 \le i \le N$)에 대해 xi, yi $\le 50$
2. (10점) $K \le 50$, 모든 $i (1 \le i \le N$)에 대해 xi, yi $\le 2\,500$
3. (12점) $K = 2$.
4. (5점) $N \le 50$.
5. (8점) $N \le 150$.
6. (9점) $N \le 600$.
7. (13점) $N \le 2\,500$.
8. (40점) 추가 제약 조건 없음.

첫 번째 줄에 두 정수 $N$과 $K$가 공백 하나를 사이로 두고 주어진다.

이후 $N$ 개의 줄이 주어진다. 이 중 $i$ 번째 줄에는 세 개의 정수 xi, yi, ki가 공백 하나 씩을 사이에 두고 주어지며, 입력으로 주어지는 각 점의 좌표 (xi, yi)와 그 점의 색깔 ki을 의미한다.

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