Nguồn ảnh: Báo tuổi trẻ Thủ Đô

Những ngày cuối năm, nhiều gia đình có thói quen dọn nhà đón Tết: lau dọn bàn thờ, sắp xếp lại đồ đạc, bỏ bớt những thứ không cần thiết để nhà cửa gọn gàng, thoáng đãng. Khi dọn, mọi người thường chia khu vực theo "mốc" trên nền nhà (ví dụ theo các ô gạch), để dễ phân công và kiểm tra xem có chỗ nào còn bừa bộn.

Bạn coi mặt sàn nhà là mặt phẳng tọa độ Oxy. Trên sàn có ~N~ vị trí cần kiểm tra (mỗi vị trí là một điểm). Hai vị trí được coi là "gần nhau" nếu chúng nằm trong cùng một vùng hình vuông song song với trục tọa độ có cạnh không vượt quá một giá trị nào đó. Nếu tìm được cặp vị trí "gần nhau" sớm, bạn có thể gom việc dọn chung một lượt.

Có ~N~ điểm phân biệt, điểm thứ ~i~ có tọa độ ~(x_i, y_i)~.

Định nghĩa khoảng cách Chebyshev giữa hai điểm:

$$d_\infty((x_1,y_1),(x_2,y_2)) = \max(|x_1-x_2|,\ |y_1-y_2|)$$

Yêu cầu: hãy tìm giá trị nguyên nhỏ nhất ~D~ sao cho tồn tại hai điểm phân biệt ~i \ne j~ thỏa:

$$d_\infty(P_i, P_j) \le D$$

Nói cách khác, ~D~ là cạnh nhỏ nhất của một hình vuông song song trục có thể chứa được ít nhất 2 điểm.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 2 \times 10^5)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~ ~( -10^9 \le x_i, y_i \le 10^9 )~.

Output

• In ra một số nguyên duy nhất là ~D~ nhỏ nhất thỏa mãn yêu cầu.

Scoring

Example input 1

5
0 0
5 5
3 4
10 0
8 2

Example output 1

2