Cập nhật hình chữ nhật

Cho ma trận $A$ kích thước $n\times m$, các phần tử được đánh chỉ số từ $1$. Ban đầu mọi phần tử $A[i][j]=0$.

Bạn cần thực hiện $q$ thao tác cập nhật hình chữ nhật. Mỗi thao tác có $5$ số nguyên $(r_1,c_1,r_2,c_2,v)$ với $r_1\le r_2$ và $c_1\le c_2$, mang ý nghĩa: cộng $v$ vào tất cả các phần tử $A[i][j]$ thỏa $r_1\le i\le r_2$ và $c_1\le j\le c_2$.

Sau khi đã thực hiện hết $q$ thao tác cập nhật, bạn nhận thêm $k$ truy vấn điểm: mỗi truy vấn là cặp $(r,c)$ — hãy in ra giá trị $A[r][c]$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n,m,q$.
• $q$ dòng tiếp theo, mỗi dòng chứa năm số nguyên $r_1,c_1,r_2,c_2,v$ mô tả một thao tác cập nhật.
• Dòng tiếp theo chứa số nguyên $k$ — số truy vấn điểm.
• $k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $r,c$ mô tả một truy vấn.

Dữ liệu ra

In ra $k$ dòng, dòng thứ $i$ là giá trị $A[r_i][c_i]$ sau khi đã áp dụng hết $q$ thao tác cập nhật.

Ràng buộc

• $1\le n,m\le {10}^3$
• $1\le q\le 2·{10}^5$
• $1\le k\le {10}^5$
• $1\le r_1\le r_2\le n$, $1\le c_1\le c_2\le m$
• $-{10}^9\le v\le {10}^9$
• $1\le r\le n$, $1\le c\le m$
• Đáp án nằm trong phạm vi kiểu số nguyên 64-bit.

Ví dụ

Ghi chú

Giá trị tuyệt đối tổng cộng có thể vượt phạm vi int 32-bit, hãy dùng kiểu số nguyên 64-bit cho mảng kết quả.