Đếm Lô Đất Vinhomes Ocean Park

Mô tả

Ban quản lý khu đô thị Vinhomes Ocean Park muốn thống kê nhanh tình trạng giao lô đất. Toàn bộ khu quy hoạch được chia thành một lưới ô vuông kích thước $R$ hàng và $C$ cột. Mỗi ô tương ứng với một lô đất, và mỗi lô ở một trong hai trạng thái: đã bàn giao (ký hiệu là 1) hoặc chưa bàn giao (ký hiệu là 0).

Khách hàng thường xuyên đến hỏi về các khu vực cụ thể, nên bạn cần xây dựng một công cụ trả lời tức thì: cho một vùng hình chữ nhật xác định bởi hàng trên cùng $r_1$, hàng dưới cùng $r_2$, cột trái $c_1$ và cột phải $c_2$, đếm xem trong vùng đó có bao nhiêu lô đã được bàn giao. Các chỉ số hàng và cột đều được đánh số từ 0.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên $R$ và $C$ ($1 \le R, C \le 1000$).
• $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên (giá trị hoặc ), mô tả sơ đồ trạng thái lô đất.

Đầu ra

• In ra $Q$ dòng, mỗi dòng là một số nguyên cho biết tổng số lô đã bàn giao trong vùng hình chữ nhật tương ứng.

Ràng buộc

• $1 \le R \times C \le 10^6$
• $1 \le Q \le 10^5$

Ví dụ

Đầu vào:

3 4 1 0 1 0 0 1 1 1 1 0 0 1 2 0 0 2 1 1 1 2 3

Đầu ra:

3 4

Giải thích:

• Truy vấn 1 0 0 2 1: xét hình chữ nhật từ hàng 0 đến hàng 2, cột 0 đến cột 1. Các phần tử là (1, 0), (0, 1), (1, 0). Số lượng lô đã bàn giao (1) là 3.
• Truy vấn 2 1 1 2 3: xét hình chữ nhật từ hàng 1 đến hàng 2, cột 1 đến cột 3. Các phần tử là (1, 1, 1), (0, 0, 1). Số lượng lô đã bàn giao là 4.