Rectangle totals: hints, no solution

A greenhouse records the yield of every plant on a rectangular grid, where yields[r][c] is the yield of the plant in row r and column c, both counted from 0. Many rectangular sections of the grid will be inspected. Each query is four numbers [top, left, bottom, right] describing the rectangle whose corner rows and columns are those numbers, all four included. Return, for every query in order, the total yield inside its rectangle. Prepare the grid once so that each query costs constant time.

Examples

Input

yields = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], queries = [[0, 0, 1, 1], [1, 1, 2, 2], [2, 0, 2, 2]]

Output

[12, 28, 24]

Note

The first rectangle holds 1 + 2 + 4 + 5, the last is the whole bottom row.

Input

yields = [[5]], queries = [[0, 0, 0, 0]]

Output

[5]

Input

yields = [[2, 0], [1, 3]], queries = [[0, 1, 1, 1], [0, 0, 1, 0]]

Output

[3, 3]

Note

Both rectangles are a single column.

Constraints

• 1 <= yields.length <= 500 and 1 <= yields[r].length <= 500, all rows equal length
• 0 <= yields[r][c] <= 9
• 0 <= queries.length <= 50000, with top <= bottom and left <= right, inside the grid

Hint 1: a nudge

If the same grid will be asked about many times, what work could you do once, before any query arrives, so that each query is quick?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing