Description

You manage an m x n farm. Each cell contains the harvest yield for that area. Multiple queries are given, each asking for the total harvest in a rectangular region from (r1, c1) to (r2, c2). Use 2D prefix sum to answer each query in O(1).

Input

Output

Constraints

• •1 <= m, n <= 1000
• •0 <= each harvest <= 100
• •0 <= r1 <= r2 < m, 0 <= c1 <= c2 < n

Examples

grid = [[1,2,3],[4,5,6],[7,8,9]], query = (0,0,1,1)

12

grid = [[1,2,3],[4,5,6],[7,8,9]], query = (1,1,2,2)

28