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.

Example

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

Output:
5 2
8 7 7

Hint

In case 2, we can divide 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