Hay $N$ puntos en un plano: $P_1 (x_1, y_1), P_2 (x_2, y_2), \dots, P_N (x_N, y_N)$. Cada punto tiene un color denotado por un número entero de $1$ a $K$.

Considera un cuadrado con lados paralelos a los ejes de coordenadas. El cuadrado es colorido si contiene puntos de todos los $K$ colores en su interior o en su borde. Se permite que el cuadrado tenga una longitud de lado de $0$, cubriendo así un solo punto.

Encuentra un cuadrado colorido con la longitud de lado mínima e imprime dicha longitud.

Entrada

La primera línea contiene dos enteros $N$ y $K$ ($2 \le N \le 10^5$, $2 \le K \le N$).

Luego siguen $N$ líneas. La $i$-ésima de estas líneas contiene tres enteros, $x_i$, $y_i$ y $c_i$: las coordenadas del $i$-ésimo punto y su color, respectivamente ($1 \le x_i, y_i \le 2.5 \cdot 10^5$, $1 \le c_i \le K$). Puedes asumir que hay al menos un punto para cada uno de los $k$ colores.

Salida

Imprime un número entero: la respuesta al problema.

Ejemplos

Entrada 1

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

Salida 1

1

Entrada 2

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

Salida 2

5

Entrada 3

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

Salida 3

0