Il y a $N$ points sur un plan : $P_1 (x_1, y_1), P_2 (x_2, y_2), \dots, P_N (x_N, y_N)$. Chaque point possède une couleur désignée par un entier compris entre $1$ et $K$.

Considérons un carré dont les côtés sont parallèles aux axes de coordonnées. Le carré est dit « coloré » s'il contient des points de toutes les $K$ couleurs à l'intérieur ou sur ses bords. Il est permis au carré d'avoir une longueur de côté de $0$, couvrant ainsi un seul point.

Trouvez un carré coloré avec la longueur de côté minimale, et affichez cette longueur.

Entrée

La première ligne contient deux entiers $N$ et $K$ ($2 \le N \le 10^5$, $2 \le K \le N$).

Ensuite, $N$ lignes suivent. La $i$-ième de ces lignes contient trois entiers, $x_i$, $y_i$ et $c_i$ : les coordonnées du $i$-ième point et sa couleur, respectivement ($1 \le x_i, y_i \le 2.5 \cdot 10^5$, $1 \le c_i \le K$). Vous pouvez supposer qu'il y a au moins un point pour chacune des $k$ couleurs.

Sortie

Affichez un entier : la réponse au problème.

Exemples

Entrée 1

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

Sortie 1

1

Entrée 2

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

Sortie 2

5

Entrée 3

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

Sortie 3

0