Description

You are given N tuples with M dimensions. You need to choose some tuples and divide them into M groups. Each tuple can be used for only once and the size of the i^th group is C_i. We define the score of the i^th group is the sum of value in the i^th dimension of the tuples in the i^th group. Your target is to firstly maximize the score of 1^st group, then maximize the score 2^nd group and so on. 

Input

The first line of the input contains an integer T(T≤50), indicating the number of cases. Each case begins with two integer N(1≤N≤10000) and M(1≤M≤10), the number of tuples and the number of groups. Then there is one line contain M integers. The i^th integer C_i (C_i >=0, sigma C_i <= N) represents the size of the i^th group. Then N lines with M integers follow. Each of them describes a tuple. The j^th integer on the i^th line T_ij (0 <=T_ij <= 10000) denotes the value of the j^th dimension of the i^th tuple.

Output

For each test case, print one line with M score of some optimal division.

Sample Input

2

4 2

2 1

3 2

2 1

2 2

1 1

4 3

1 1 2

8 7 1

8 7 2

8 7 4

8 2 3

Sample Output

5 2

8 7 7

Hint

In case 2, we can dive the group like:

Group 1: (8, 7, 2)  score = 8

Group 2: (8, 7, 1)  score = 7

Group 3: (8, 7, 4), (8, 2, 3) score = 4 + 3 = 7