2D prefix sum

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

Input

Output

Examples

Constraints

To check your solution you need to sign in

Sign in to continue

Sign in to continue

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

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

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