평면 위에 $N$개의 점 $P_1 (x_1, y_1), P_2 (x_2, y_2), \dots, P_N (x_N, y_N)$이 있다. 각 점은 $1$부터 $K$까지의 정수로 나타내는 색상을 가진다.

좌표축과 평행한 변을 가진 정사각형을 고려하자. 이 정사각형 내부에 또는 경계 위에 $K$가지 색상의 점이 모두 포함되어 있으면 이 정사각형을 '컬러풀(colorful)'하다고 한다. 정사각형의 변 길이는 $0$일 수 있으며, 이 경우 한 점만을 포함한다.

컬러풀한 정사각형 중 최소 변 길이를 찾아 그 길이를 출력하시오.

입력

첫 번째 줄에는 두 정수 $N$과 $K$ ($2 \le N \le 10^5$, $2 \le K \le N$)가 주어진다.

그다음 $N$개의 줄이 주어진다. $i$번째 줄에는 $i$번째 점의 좌표와 색상을 나타내는 세 정수 $x_i, y_i, c_i$ ($1 \le x_i, y_i \le 2.5 \cdot 10^5$, $1 \le c_i \le K$)가 주어진다. 각 $k$ 색상에 대해 적어도 하나의 점이 존재한다고 가정할 수 있다.

출력

문제의 정답인 정수 하나를 출력하시오.

예제

입력 1

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

출력 1

1

입력 2

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

출력 2

5

입력 3

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

출력 3

0