平面上有 $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