Xây dựng lãnh địa
Đề bài
Mô tả
Thục đã chơi Age of Empires 2 được vài tháng. Trong trò chơi này, Thục đóng vai nhà vua, ra lệnh cho dân làng xây dựng các lãnh địa cho vương quốc. Khu vực chơi được biểu diễn bằng một bảng kích thước , trong đó giao của hàng thứ và cột thứ được ký hiệu là ô .
Trong trò chơi, giá trị tài nguyên của mỗi ô là , trong đó là một tham số nguyên dương được cho khi bắt đầu trò chơi.
Thục đã lên kế hoạch xây lãnh địa trên khu vực chơi để thu tài nguyên. Lãnh địa thứ được biểu diễn bằng một hình chữ nhật với tọa độ (, ), nghĩa là Thục sẽ chiếm mọi ô thỏa mãn và . Trò chơi không giới hạn việc xây dựng, vì vậy các lãnh địa có thể có chung một số ô.
Đáng tiếc, hôm nay Thục phát hiện ra rằng tài nguyên của một ô không thể được thu quá một lần, nên cách tính tổng tài nguyên của Thục không còn đúng nữa. Hãy giúp Thục tính lại tổng giá trị tài nguyên thực sự mà Thục thu được theo kế hoạch.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và : số lãnh địa trong kế hoạch và tham số .
- Dòng thứ trong dòng tiếp theo chứa bốn số nguyên là tọa độ của lãnh địa thứ .
Dữ liệu ra
In ra một số nguyên là tổng giá trị tài nguyên thực sự Thục thu được, lấy theo modulo .
Ràng buộc
- , .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 1 2 2 1 2 1 3 |
34 | Các ô bị chiếm là , , , , với giá trị . Hai lãnh địa có chung ô , ô này chỉ được tính một lần. |
| 3 3 1 1 1 1 1 1 1 1 2 2 3 3 |
1226 | Ví dụ bổ sung: hai lãnh địa đầu trùng nhau, chỉ gồm ô (giá trị ). Lãnh địa thứ ba gồm các ô , , , với giá trị , tổng cộng . |
Bình luận