На плоскости задано $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$). Можно считать, что для каждого из $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