def sum_2d(grid):
    H, W = len(grid), len(grid[0])
    S = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        for j in range(W):
            S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + grid[i][j]
    return S

def cal_2d(S, i0, j0, i1, j1):
    return S[i1+1][j1+1] - S[i0][j1+1] - S[i1+1][j0] + S[i0][j0]