Tòa nhà

Thành phố nơi Alice sinh sống có $n$ 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à $u$ và $v$ gọi là độc đạo nếu như sau khi đi từ $u$ sang $v$ qua lối đi này thì không có cách đi nào quay trở lại $u$ thông qua các lối đi tắt khác ngoài lối đi tắt từ $v$ về $u$.

Với mỗi cặp tòa nhà $(u,v)$ 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ừ $u$ Alice có thể tham quan được tối đa $d_u$ tòa nhà, và nếu xuất phát từ $v$ Alice có thể tham quan được tối đa $d_v$ tòa nhà. Khoảng chênh lệch giữa $d_u$ và $d_v$ là giá trị $|d_u-d_v|$.

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à $(u,v)$ có lối đi tắt độc đạo sao cho khoảng chênh lệch giữa $d_u$ và $d_v$ là nhỏ nhất.

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên dương $n$ là số lượng tòa nhà cao tầng;
• Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa $4$ số nguyên không âm $x_i,y_i,p_i,q_i$ với $(x_i,y_i)$ là tọa độ của đỉnh trái trên và $(p_i,q_i)$ 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ứ $i$ trên bản đồ quy hoạch. Dữ liệu đảm bảo $x_i<p_i$ và $y_i>q_i$ 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

In 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ố $-1$.

Ràng buộc

• $1\le n\le {10}^5$;
• $0\le x_i<p_i\le {10}^9$, $0\le q_i<y_i\le {10}^9$;
• Hai hình chữ nhật bất kỳ có thể tiếp xúc (chung cạnh hoặc chung đỉnh) nhưng phần trong không giao nhau.

Subtasks

• Subtask 1 ($30\%$ số test, $30\%$ số điểm): $n\le {10}^3$, các tọa độ không vượt quá ${10}^9$;
• Subtask 2 ($30\%$ số test, $30\%$ số điểm): $n\le {10}^5$, các tọa độ không vượt quá ${10}^3$;
• Subtask 3 ($40\%$ số test, $40\%$ số điểm): $n\le {10}^5$, các tọa độ không vượt quá ${10}^9$.

Ví dụ