Thành phố nơi Alice sinh sống có toà nhà. Trên bản thiết kế, mặt bằng nền mỗi tòa nhà đều là hình chữ nhật có các cạnh song song với trục tọa độ, với các đỉnh đều có tọa độ nguyên trên hệ trục tọa độ. Hai tòa nhà gọi là liền kề nếu có hai đường biên của hai hình chữ nhật mặt nền tương ứng hai tòa nhà đó có ít nhất một điểm chung. Để thuận tiện đi lại giữa các tòa nhà, người ta xây dựng một lối đi tắt hai chiều giữa mỗi cặp tòa nhà liền kề.
Alice rất thích thú với cách thiết kế các tòa nhà của thành phố và thường xuyên đi lại giữa các tòa nhà thông qua các lỗi đi tắt này. Sau một thời gian khám phá, Alice nhận thấy có một số lối đi tắt là độc đạo. Một lối đi tắt giữa hai tòa nhà và gọi là độc đạo nếu như sau khi đi từ sang qua lối đi này thì không có cách đi nào quay trở lại thông qua các lối đi tắt khác ngoài lối đi tắt từ về .
Với mỗi cặp tòa nhà có lối đi tắt là độc đạo, Alice tiếp tục khám phá nếu như đóng cửa lối đi độc đạo này thì xuất phát từ Alice có thể tham quan được tối đa tòa nhà, và nếu xuất phát từ Alice có thể tham quan được tối đa tòa nhà. Khoảng chênh lệch giữa và là giá trị .
Yêu cầu: Biết tọa độ các đỉnh hình chữ nhật mặt nền tương ứng của các tòa nhà, hãy giúp Alice tìm cặp tòa nhà có lỗi đi tắt độc đạo sao cho khoảng chênh lệch giữa và là nhỏ nhất.
Dữ liệu vào:
Dòng thứ nhất chứa một số nguyên dương là số lượng tòa nhà cao tầng;
Dòng thứ trong số dòng tiếp theo chứa số nguyên không âm với là tọa độ của đỉnh trái trên và là tọa độ của đỉnh phải dưới của hình chữ nhật biểu thị mặt nền tòa nhà thứ trên bản đồ quy hoạch. Dữ liệu đảm bảo Và > và hai hình chữ nhật bất kỳ có thể tiếp xúc nhưng không giao nhau.
Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là khoảng chênh lệch nhỏ nhất tìm được. Nếu không tổn tại lối đi tắt độc đạo thì in ra số .
Giới hạn:
Có số test ứng với số điểm của bài thỏa mãn điều kiện: , các tọa độ không vượt quá ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: , các tọa độ không vượt quá ;
số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: , các tọa độ không vượt quá .
Vị dụ:
Dữ liệu vào:
6
1 3 4 1
4 1 8 0
6 2 9 1
4 4 8 2
5 6 7 4
6 7 9 6
Dữ liệu ra:
2
Giải thích:
Lối đi độc đạo là lối đi giữa cặp tòa nhà và . Nếu đóng cửa lối đi độc đạo qua , ta có và , do đó . Nếu đóng cửa lối đi độc đạo qua , ta có và , do đó .
