平面上有 $N$ 個點：$P_1 (x_1, y_1), P_2 (x_2, y_2), \dots, P_N (x_N, y_N)$。每個點都有一個顏色，以 $1$ 到 $K$ 之間的整數表示。

考慮一個邊平行於座標軸的正方形。如果該正方形的內部或邊界上包含了所有 $K$ 種顏色的點，則稱該正方形為「彩色」的。正方形允許邊長為 $0$，即僅覆蓋單一個點。

請找出一個邊長最小的彩色正方形，並輸出該邊長。

輸入格式

第一行包含兩個整數 $N$ 和 $K$ ($2 \le N \le 10^5$, $2 \le K \le N$)。

接下來有 $N$ 行。第 $i$ 行包含三個整數 $x_i, y_i$ 和 $c_i$，分別代表第 $i$ 個點的座標及其顏色 ($1 \le x_i, y_i \le 2.5 \cdot 10^5$, $1 \le c_i \le 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