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

• # 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 `(i, j)` is the sum of all the elements between the corner `(0, 0)` and the element `(i, j)`. In other words, it’s the sum of elements of the submatrix with corners `(0, 0)`, `(i, 0)`, `(i, j)`, and `(0, j)`.
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