Restore the matrix

The magical world of has now upgraded and stores in information in 2D prefix sum arrays. This helps them move faster and saves a lot of time. Yet, as usual, they sometimes lose the initial arrays and get stuck. Can you help them restore the initial 2D array from a given 2D prefix sum matrix?

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 prefix sum matrix .

Output

The program should print r lines containing c numbers representing the initial matrix.

Examples

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

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 15 MB

To check your solution you need to sign in
Sign in to continue