# 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: 6 seconds

Memory limit: 512 MB

Output limit: 15 MB