Bờm và Cuội gần đây đã tìm thấy một bảng trò chơi xếp hình domino cổ đại. Bảng có dạng hình chữ nhật được chia thành các lưới ô vuông kích thước , các hàng được đánh số từ đến , các cột được đánh số từ đến ( và là các số tự nhiên lẻ). Bảng được lấp đầy bởi quân domino, mỗi domino chiếm hai ô liền kề, một số domino được đặt theo chiều ngang, một số lại được đặt theo chiều dọc, và rõ ràng sẽ có một ô trên bảng không bị quân domino nào đặt lên.
Bờm và Cuội nhìn vào bảng này và nghĩ về tất cả những nhiệm vụ tuyệt vời có thể nghĩ ra từ bảng xếp hình domino này. Một ý tưởng ngay lập tức nảy ra với họ. Với cách đặt các ô domino trên một bảng hiện tại, thì có thể di chuyển được bao nhiêu quân domino từ vị trí ban đầu của chúng đến vị trí khác, hay có bao nhiêu quân domino có thể thay đổi vị trí?
Ví dụ, đối với một bảng được sắp xếp như trên, ô trống ở vị trí , trước tiên chúng ta có thể di chuyển domino đặt trên các ô lên trên và do đó, ô trống sẽ là ô . Sau khi di chuyển nó, nhiều khả năng hơn sẽ mở ra, vì vậy giả sử ta có thể di chuyển domino ở các ô lên trên hoặc domino ở về phía phải. Trong tổng số quân cờ domino trên bảng này, tám quân trong đó
có thể được di chuyển khỏi vị trí ban đầu của chúng theo một cách nào đó.
Hãy viết một chương trình đếm xem có bao nhiêu quân cờ domino khác nhau có thể được di chuyển ra vị trí khác theo một cách nào đó.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và là số hàng và số cột của bảng, cả hai đều là các số lẻ ;
Dòng thứ trong tiếp theo, mỗi dòng chứa bốn số nguyên dương tương ứng là vị trí đặt của quân domino thứ trên bảng là hai ô và , với là chỉ số hàng và là chỉ số cột. Dữ liệu đảm bảo các quân domino không xếp chồng lên nhau, không vượt quá giới hạn của bảng, và hai ô của một quân domino đặt lên là hai ô kề nhau trên bảng.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là số quân domino có thể di chuyển ra vị trí khác với vị trí ban đầu.
