Sau khi giành chiến thắng trong một trận đánh lớn, vua Jaguar muốn xây một kim tự tháp vừa làm đài tưởng niệm chiến thắng, vừa làm lăng mộ cho những người lính dũng cảm đã hy sinh. Kim tự tháp sẽ được xây ngay trên chiến trường, có đáy hình chữ nhật gồm \(a\) cột và \(b\) hàng. Bên trong kim tự tháp, ở ngang mặt đất, có một gian mộ hình chữ nhật nhỏ hơn gồm \(c\) cột và \(d\) hàng, chứa thi hài và vũ khí của những người lính đã ngã xuống.

Các kiến trúc sư của nhà vua đã khảo sát chiến trường dưới dạng một lưới gồm \(m\) cột và \(n\) hàng, đồng thời đo độ cao của từng ô bằng một số nguyên.

Cả kim tự tháp lẫn gian mộ phải phủ trọn các ô của lưới, với các cạnh song song với các cạnh của chiến trường. Độ cao của các ô bên trong gian mộ phải được giữ nguyên, còn phần địa hình thuộc đáy kim tự tháp ở bên ngoài gian mộ sẽ được san bằng bằng cách chuyển cát từ các ô cao xuống các ô thấp. Độ cao cuối cùng của nền là độ cao trung bình của tất cả các ô thuộc đáy kim tự tháp, không tính các ô của gian mộ. Các kiến trúc sư có thể đặt gian mộ ở bất kỳ vị trí nào bên trong kim tự tháp, miễn là quanh gian mộ luôn có một bức tường dày ít nhất một ô.

Hãy giúp các kiến trúc sư chọn vị trí đặt kim tự tháp trên chiến trường và vị trí đặt gian mộ bên trong kim tự tháp sao cho, với các kích thước đã cho, độ cao cuối cùng của nền lớn nhất có thể.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa sáu số nguyên cách nhau bởi dấu cách, theo thứ tự \(m\), \(n\), \(a\), \(b\), \(c\), \(d\).
• Mỗi dòng trong \(n\) dòng tiếp theo chứa \(m\) số nguyên cách nhau bởi dấu cách, là độ cao các ô trên một hàng của lưới. Dòng đầu tiên trong số này ứng với hàng trên cùng, tức hàng \(1\); dòng cuối ứng với hàng dưới cùng, tức hàng \(n\). Trên mỗi dòng, các độ cao được liệt kê theo thứ tự từ cột \(1\) đến cột \(m\).

Dữ liệu ra

Ghi ra đầu ra chuẩn hai dòng:

• Dòng đầu chứa hai số nguyên cách nhau bởi một dấu cách, chỉ góc trên bên trái của đáy kim tự tháp: số thứ nhất là cột, số thứ hai là hàng.
• Dòng thứ hai chứa hai số nguyên cách nhau bởi một dấu cách, chỉ góc trên bên trái của gian mộ bên trong kim tự tháp: số thứ nhất là cột, số thứ hai là hàng.

Nếu có nhiều cách bố trí tối ưu, bạn có thể đưa ra bất kỳ cách nào trong số đó.

Ràng buộc

• \(3 \le m \le 1\,000\).
• \(3 \le n \le 1\,000\).
• \(3 \le a \le m\).
• \(3 \le b \le n\).
• \(1 \le c \le a-2\).
• \(1 \le d \le b-2\).
• Mọi độ cao đều là số nguyên từ \(1\) đến \(100\).

Phân nhóm

Trong một tập các bộ dữ liệu kiểm tra có tổng cộng \(30\) điểm, mỗi lần chạy đều đồng thời thỏa mãn \(3 \le m \le 10\) và \(3 \le n \le 10\).

Ví dụ

8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2

4 1
6 2

Nguồn

IOI 2006, ngày thi thứ nhất: Pyramid, bản tiếng Anh 1.2. Tác giả đề bài: Hugo Ryckeboer (Argentina).