Farmer John đã quyết định cải tạo trang trại để đơn giản hóa hình dạng của nó. Trước đây, đàn bò của ông gặm cỏ trong hai đồng cỏ hình chữ nhật có hàng rào bao quanh. Farmer John muốn thay chúng bằng một đồng cỏ hình vuông duy nhất có kích thước nhỏ nhất nhưng vẫn bao phủ toàn bộ những khu vực trong trang trại từng được hai hàng rào cũ bao quanh.

Hãy giúp Farmer John xác định diện tích nhỏ nhất cần có của đồng cỏ hình vuông mới để khi được đặt ở vị trí thích hợp, nó vẫn có thể bao phủ toàn bộ diện tích từng được hai đồng cỏ hình chữ nhật cũ bao phủ. Các cạnh của đồng cỏ hình vuông phải song song với các trục \(x\) và \(y\).

Dữ liệu vào

Dòng đầu tiên mô tả một trong hai đồng cỏ hình chữ nhật ban đầu bằng bốn số nguyên cách nhau bởi dấu cách \(x_1\), \(y_1\), \(x_2\), \(y_2\), mỗi số nằm trong khoảng \(0 \ldots 10\). Góc dưới bên trái của đồng cỏ là điểm \((x_1,y_1)\) và góc trên bên phải là điểm \((x_2,y_2)\), trong đó \(x_2>x_1\) và \(y_2>y_1\).

Dòng thứ hai có cùng định dạng bốn số nguyên như dòng đầu tiên và mô tả đồng cỏ hình chữ nhật ban đầu thứ hai. Đồng cỏ này không chồng lấn và cũng không tiếp xúc với đồng cỏ thứ nhất.

Dữ liệu ra

In một dòng chứa diện tích nhỏ nhất cần có của một đồng cỏ hình vuông có thể bao phủ toàn bộ những khu vực ban đầu được hai đồng cỏ hình chữ nhật bao quanh.

Ví dụ

6 6 8 8
1 8 4 9

49

Nguồn

USACO 2016 December Contest, Bronze — Square Pasture. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=663