Matrix Summation and 2D Prefix Sum Inversion

A high-frequency analytics database at Citadel stores 2D aggregated trade volumes in a prefix-sum matrix $B$ of dimension $M \times N$. The matrix $B$ was generated from an original raw execution volume matrix $A$ according to the 2D prefix sum formula: $B[i][j] = \sum_{r=0}^i \sum_{c=0}^j A[r][c]$ where $0 \le i < M$ and $0 \le j < N$.

Your Task

Implement restore_matrix(b: list[list[int]]) -> list[list[int]] that reconstructs the original matrix $A$ from $B$ in $\mathcal{O}(M \cdot N)$ time using the principle of inclusion-exclusion.

Constraints

• $1 \le M, N \le 1000$
• $-10^9 \le B[i][j] \le 10^9$
• Input matrix $B$ is non-empty.

Examples

b = [
    [2, 5],
    [7, 17]
]
# A[0][0] = 2
# A[0][1] = 5 - 2 = 3
# A[1][0] = 7 - 2 = 5
# A[1][1] = 17 - 5 - 7 + 2 = 7
# Output: [[2, 3], [5, 7]]