平面上に $N$ 個の点 $P_1 (x_1, y_1), P_2 (x_2, y_2), \dots, P_N (x_N, y_N)$ があります。各点は $1$ から $K$ までの整数で表される色を持っています。

座標軸に平行な辺を持つ正方形を考えます。この正方形の内部または境界上に $1$ から $K$ までのすべての色の点が含まれているとき、その正方形を「カラフル」であると呼びます。正方形の辺の長さは $0$ でもよく、その場合は一点のみを覆うことになります。

カラフルな正方形のうち、辺の長さが最小となるものを求め、その長さを出力してください。

入力

入力の最初の行には、2つの整数 $N$ と $K$ ($2 \le N \le 10^5$, $2 \le K \le N$) が含まれます。

続く $N$ 行には、各点の情報が与えられます。$i$ 番目の行には、3つの整数 $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つの点が存在すると仮定して構いません。

出力

問題の答えである整数を1つ出力してください。

入出力例

入力 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