Given a mXn matrix, find a path from the first cell (0,0) to the last cell (m-1,n-1) such that the sum of the elements in the path is maximum. You can only go to the cell in the right or to the cell below from the current position. print the maximum sum and the path which obtained that sum.

Input

First line- no of test cases

each test case conatins the order(m,n) of the matrix followed by the elements.

Output

for each test case-

print the maximum sum in the first line

in the next line print the path(just the elements one by one).

Example

Input:
2

2 2

10 20

10 30

3 2

5 0
0 -3
-2 -3

Output:
60

10 20 30

0

5 0 -2 -3