#1484. Đếm phần thưởng (Mã bài: BONUS)

Alice là người chiến thắng trong một cuộc thi “Tìm hiểu kiến thức vũ trụ” và được nhận phần thưởng theo cách sau:

Các phần thưởng được bố trí trên một bảng có kích thước . Các dòng của bảng được đánh số từ đến , từ trên xuống dưới và các cột của bảng được đánh số từ đến , từ trái qua phải. Ô nằm trên giao của dòng và cột được gọi là và trên ô đó chứa một món quà loại . Giữa hai ô và bất kì chứa cùng một loại quà, luôn tồn tại một đường đi qua các ô chung cạnh cũng chứa loại quà đó.

Để nhận phần thưởng, Alice cần trả lời truy vấn : “Có bao nhiêu loại quà khác nhau gồm các ô được giới hạn bởi hình chữ nhật có góc trái trên ở ô và góc phải dưới ở ô ?”.

Có truy vấn như vậy, Alice cần trả lời được tất cả các câu hỏi để nhận thưởng. Hãy giúp Alice trả lời các truy vấn này.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương () là kích thước của bảng.
• Dòng thứ trong dòng tiếp theo, mỗi dòng chứa số nguyên dương. Số thứ là ().
• Dòng tiếp theo chứa số () là số truy vấn.
• dòng tiếp theo, mỗi dòng ghi một truy vấn gồm 4 số nguyên dương ().

Kết quả: Với mỗi truy vấn, in ra trên một dòng là kết quả tìm được

Ví dụ:

Dữ liệu:

4 4
1 2 2 3
1 2 4 5
1 2 4 4
1 2 2 4	
4	
2 3 2 3	
2 4 3 4	
1 2 1 4	
4 1 4 3

Kết quả:

1
2
2
2

Giới hạn:

• Subtask 1 (25%):
• Subtask 2 (25%):
• Subtask 3 (25%):
• Subtask 4 (25%): không có ràng buộc nào thêm