Thành phố FutureLand là một khu đô thị hiện đại được quy hoạch trên một bản đồ dạng lưới khổng lồ gồm cột (trục Đông-Tây) và hàng (trục Bắc-Nam). Tổng cộng có lô đất. Các cột và hàng được đánh số bắt đầu từ . Tọa độ của lô đất nằm ở cột thứ , hàng thứ được ký hiệu là .
Ban đầu, toàn bộ các lô đất đều là đất trống (chưa được xây dựng). Ủy ban thành phố phê duyệt dự án xây dựng đường giao thông. Mỗi dự án sẽ trải nhựa lên một loạt các lô đất liên tiếp.
Các dự án xây dựng được chia làm ba loại:
Xây đường ngang: Trải nhựa cho một đoạn đường thẳng theo phương ngang. Cụ thể, cho hai tọa độ và với , dự án sẽ chiếm dụng tất cả các lô đất nằm giữa hai tọa độ này (bao gồm cả hai đầu mút).
Xây đường dọc: Trải nhựa cho một đoạn đường thẳng theo phương dọc. Cụ thể, cho hai tọa độ và với , dự án sẽ chiếm dụng tất cả các lô đất nằm giữa hai tọa độ này (bao gồm cả hai đầu mút).
Xây cầu vượt chéo: Trải nhựa cho một đường chéo đặc biệt. Cụ thể, cho hai tọa độ và với , dự án sẽ chiếm dụng tất cả các lô đất có dạng (với ) nằm trên đường chéo nối hai điểm này. Do chi phí cao, loại dự án này được phê duyệt không quá 5 lần.
Lưu ý rằng một lô đất có thể bị trải nhựa nhiều lần bởi các dự án khác nhau (ví dụ: tại ngã tư nơi đường ngang và đường dọc cắt nhau), nhưng diện tích chiếm dụng vẫn chỉ tính là 1 lô đất.
Nhiệm vụ của bạn là tính toán xem sau khi hoàn thành dự án, tổng cộng có bao nhiêu lô đất đã được trải nhựa.
Dữ liệu:
Dòng đầu tiên chứa một số nguyên , biểu thị mã số của test ( là ví dụ).
Dòng thứ hai chứa ba số nguyên dương , lần lượt là kích thước chiều ngang, chiều dọc của thành phố và số lượng dự án.
dòng tiếp theo, mỗi dòng chứa năm số nguyên dương . Trong đó là xây đường ngang, là xây đường dọc, là xây cầu vượt chéo. là tọa độ giới hạn của dự án.
Kết quả: Một dòng duy nhất chứa một số nguyên, là tổng số lượng lô đất đã được trải nhựa trên bản đồ thành phố.
Ví dụ:
Dữ liệu:
0
5 5 3
1 1 3 5 3
2 3 1 3 5
3 1 1 5 5
Kết quả:
13
Giới hạn: , , , , và có tối đa 5 dự án loại 3.
Subtask #1: số điểm có .
Subtask #2: số điểm có .
Subtask #3: số điểm có và chỉ có dự án loại 1.
Subtask #4: số điểm có và không có dự án loại 3.
Subtask #5: số điểm còn lại không có ràng buộc bổ sung.
