Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation

• # 2D prefix sum

Given a large 2D array of numbers with `r` rows and `c` columns, you are asked to calculate the 2D prefix sum of that matrix. 2D prefix sum at a location `(r, c)` is the sum of all the elements between the corner `(0, 0)` and the element `(r, c)`. In other words, it’s the sum of elements of the submatrix with corners `(0, 0)`, `(r, 0)`, `(r, c)`, and `(0, c)`.
Can you calculate the 2D prefix sum for all the locations in the matrix efficiently?

 + + + + ㅤ ㅤ ㅤ + + + + ㅤ ㅤ ㅤ + + + + ㅤ ㅤ ㅤ + + + + ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ ㅤ

#### Input

The first line of the input contains two integers - the number of rows in the matrix `r` and the number of columns `c` (1 ≤ r, c ≤ 1000).
The next `r` lines contain `c` integers separated by a space, that represent the elements in the matrix .

#### Output

The program should print `r` lines containing `c` numbers representing the 2D prefix sum matrix.

#### Examples

 Input Output 3 5 1 2 -3 4 6 -1 3 8 4 0 0 1 -2 0 5 1 3 0 4 10 0 5 10 18 24 0 6 9 17 28

#### Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 15 MB