Security Game

Albert enjoys a board game called "Security Game". The goal is to protect $M$ buildings with $N$ security robots. The game has the following rules.

1. Each robot can protect up to $B$ different buildings at the same time.
2. Not every robot can protect every building. The $i$-th robot can protect $g_i$ different buildings, denoted $x_{i,j}$ ($1 \le j \le g_i$, $1 \le x_{i,j} \le M$).
3. The $k$-th building must be protected by at least $L_k$ and at most $U_k$ different robots. The score of each building is the number of robots guarding it.
4. If the robots are placed while following all the rules above, the game score is the sum of the building scores. If no placement follows all the rules, the game score is -1.

For convenience, $S_b$ is defined as the maximum game score Albert can get when $B = b$ ($1 \le B \le M$).

For example, let $N = M = 3$, $g = [2, 2, 2]$, $x = [[1, 2], [1, 3], [2, 3]]$, $L = [1, 1, 1]$, and $U = [3, 3, 3]$.

• If $B = 1$, the maximum score is 3. Robot 1 protects building 2, robot 2 protects building 1, and robot 3 protects building 3. Each building scores 1, so the game score is 3.
• If $B = 2$, the maximum score is 6. Robot 1 protects buildings 1 and 2, robot 2 protects buildings 1 and 3, and robot 3 protects buildings 2 and 3. Each building scores 2, so the game score is 6.
• If $B = 3$ or more, no placement scores more than 6. Therefore $S = [3, 6, 6]$.

As another example, let $N = 4$, $M = 3$, $g = [3, 1, 1, 1]$, $x = [[1, 2, 3], [1], [1], [3]]$, $L = [1, 2, 1]$, and $U = [2, 2, 2]$.

• Building 2 has $L_2 = U_2 = 2$, so exactly 2 different robots must protect it.
• Only robot 1 can protect building 2, so the game score is -1 regardless of the value of $B$.
• In this case $S = [-1, -1, -1]$.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$ and $M$, separated by a space. The next $N$ lines each contain $g_i$, the number of buildings where the $i$-th robot can be placed, followed by the $g_i$ building numbers $x_{i,1}, x_{i,2}, \dots, x_{i,g_i}$, separated by spaces. In other words, each of these lines contains $g_i + 1$ integers. The next $M$ lines each contain a pair of integers $L_k$ and $U_k$, the minimum and maximum number of robots that must be placed on the $k$-th building.

For each test case, print $S_1, S_2, \dots, S_M$ separated by spaces on a single line.

• $1 \le T \le 10$
• $1 \le N, M \le 200$
• $\sum_{1 \le i \le N} g_i \le 5000$
• For each $i$ with $1 \le i \le N$:
  • $1 \le g_i \le M$
  • $1 \le x_{i,1}, x_{i,2}, \dots, x_{i,g_i} \le M$
  • $x_{i,1}, x_{i,2}, \dots, x_{i,g_i}$ contain no duplicate values
• For each $k$ with $1 \le k \le M$: $1 \le L_k \le U_k \le N$