game-1

There are $N$ games on an online platform, and we know their prices $p_1~ \ldots ~ p_N$. There are also $M$ friends on this platform, and we know how much money each has in their (online) wallet ($v_k$) and which games they already own $g_1,~~\ldots,~~g_{a_k}~~(a_k\ge 0)$. The group wants to play the same game together. Money cannot be gifted, but games can be - any number of them. For each game, we want to know the minimum total money spending required if they want to play that game together. Create a report of this $s_1,\ldots,s_N$!

Input specification

The first line contains $T$, the number of test cases. Description of a test case: First line: $N~~ M$ (number of games and friends). Next line: game prices $p_1~ \ldots ~ p_N$. Next $M$ lines: the numbers $v_k~~ g_1~~ \ldots ~~g_{a_k}~~~~(k=1,\ldots,M)$.

Output specification

$T$ lines, each containing the numbers $s_1 ~ \ldots ~ s_N$ for that test case. If it’s not possible for everyone to get a particular game, output $-1$.

Constraints

$1\le T \le 100$
$1\le N \le 10\_000$
$1\le M \le 1\_000$
$1\le p_k \le 1\_000$
$0\le v_k \le 10\_000$
$0\le a_k \le 10\_000$

Sample input 1

1. 4
2. 4 3
3. 15 8 20 25
4. 0 1 2
5. 15 3 4
6. 10 1
7. 4 3
8. 22 22 22 22
9. 0 1 2 3 4
10. 0 1 2 3
11. 0 1 2
12. 4 3
13. 22 22 22 22
14. 44 1 2 3 4
15. 0 1 2 3
16. 0 1 2
17. 4 4
18. 22 22 22 22
19. 44 1 2 3 4
20. 0 1 2 3
21. 0 1 2
22. 22

Sample output 1

1. 15 16 -1 -1
2. 0 0 -1 -1
3. 0 0 22 44
4. 22 22 44 66