Na płaszczyźnie znajduje się $N$ punktów: $P_1 (x_1, y_1), P_2 (x_2, y_2), \dots, P_N (x_N, y_N)$. Każdy punkt ma kolor oznaczony liczbą całkowitą od $1$ do $K$.

Rozważmy kwadrat o bokach równoległych do osi układu współrzędnych. Kwadrat jest kolorowy, jeśli zawiera wewnątrz lub na swoim brzegu punkty wszystkich $K$ kolorów. Dopuszcza się kwadrat o długości boku $0$, który pokrywa tylko pojedynczy punkt.

Znajdź kolorowy kwadrat o minimalnej długości boku i wypisz tę długość.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $N$ oraz $K$ ($2 \le N \le 10^5$, $2 \le K \le N$).

Następnie następuje $N$ linii. $i$-ta z tych linii zawiera trzy liczby całkowite $x_i$, $y_i$ oraz $c_i$: odpowiednio współrzędne $i$-tego punktu oraz jego kolor ($1 \le x_i, y_i \le 2.5 \cdot 10^5$, $1 \le c_i \le K$). Można założyć, że istnieje co najmniej jeden punkt dla każdego z $K$ kolorów.

Wyjście

Wypisz jedną liczbę całkowitą: odpowiedź na zadanie.

Przykład

Wejście 1

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

Wyjście 1

1

Wejście 2

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

Wyjście 2

5

Wejście 3

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

Wyjście 3

0