Có $N$ điểm trên mặt phẳng: $P_1 (x_1, y_1), P_2 (x_2, y_2), \dots, P_N (x_N, y_N)$. Mỗi điểm có một màu được biểu thị bằng một số nguyên từ $1$ đến $K$.

Xét một hình vuông có các cạnh song song với các trục tọa độ. Hình vuông được gọi là "colorful" (nhiều màu) nếu nó chứa các điểm của tất cả $K$ màu ở bên trong hoặc trên biên của nó. Hình vuông được phép có độ dài cạnh bằng $0$, khi đó nó chỉ bao phủ một điểm duy nhất.

Hãy tìm hình vuông colorful có độ dài cạnh nhỏ nhất và in ra độ dài đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($2 \le N \le 10^5$, $2 \le K \le N$).

Tiếp theo là $N$ dòng. Dòng thứ $i$ chứa ba số nguyên $x_i, y_i$ và $c_i$: lần lượt là tọa độ và màu của điểm thứ $i$ ($1 \le x_i, y_i \le 2.5 \cdot 10^5$, $1 \le c_i \le K$). Bạn có thể giả định rằng có ít nhất một điểm cho mỗi màu trong $K$ màu.

Dữ liệu ra

In ra một số nguyên duy nhất: đáp án của bài toán.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Dữ liệu vào 2

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

Dữ liệu ra 2

5

Dữ liệu vào 3

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

Dữ liệu ra 3

0