At P University, many courses offer small-group sessions, and students are free to choose these sessions based on their needs. However, the capacity of these small-group sessions is not infinite, so not every student can enroll in their preferred session.

This semester, a total of $n$ students have enrolled in Course A, which offers $m$ small-group sessions. The $i$-th session has a capacity of $b_i$. Each student $i$ has a preference sequence $a_{i,1} \sim a_{i,k_i}$, where $a_{i,1}$ represents the session with the highest preference and $a_{i,k_i}$ represents the session with the lowest preference. If a session $j$ is not in this sequence, it means student $i$ cannot attend session $j$.

Students choose their sessions in the order $1 \sim n$. Each student will choose the session with the highest priority that is not yet full. If all sessions in their sequence $a_{i,1} \sim a_{i,k_i}$ are already full, the student will not choose any session.

Given the preference sequence for each student, reorder the students such that the number of students who successfully enroll in a session is maximized, and provide the construction.

Input

The input is read from standard input.

The first line contains a positive integer $T (1 \leq T \leq 500)$, representing the number of test cases.

For each test case, the first line contains two positive integers $n, m (1 \leq n, m \leq 500)$, representing the number of students and the number of small-group sessions.

The next line contains $m$ non-negative integers $b_i (0 \leq b_i \leq 500)$, representing the capacity of each small-group session.

The next $n$ lines each start with a non-negative integer $k_i (0 \leq k_i \leq m)$, followed by $k_i$ distinct positive integers $a_{i,1} \sim a_{i,k_i} (1 \leq a_{i,j} \leq m)$, representing the preference sequence.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$, and the sum of $m$ over all test cases does not exceed $500$.

Output

Output to standard output.

For each test case, output two lines. The first line contains an integer $ans$, representing the maximum number of students who can enroll. The second line contains $n$ integers, representing a permutation of $1 \sim n$ that achieves this result. If there are multiple valid solutions, any one is acceptable.

Examples

Input 1

3
5 5
1 1 1 1 1
4 1 3 2 4
1 5
4 3 4 2 1
2 3 5
1 1
5 3
1 2 2
2 1 2
2 1 2
2 1 3
2 1 3
2 1 3
5 5
1 1 1 1 1
2 1 2
2 5 4
2 3 2
2 4 3
2 5 1

Output 1

5
2 4 5 1 3
5
5 1 2 3 4
5
1 5 2 4 3

Note

For the first test case, following the given order, student $2$ chooses $5$, then student $4$ chooses $3$, student $5$ chooses $1$. Student $1$ attempts to choose $1$ and $5$, but both are full, so they choose $2$. Student $3$ attempts to choose $3$, but it is full, so they choose $4$. The solution for this test case is not unique; for example, $\{2, 5, 4, 3, 1\}$ is also a valid solution.

For the second test case, $\{1, 2, 3, 4, 5\}$ is not a valid solution. If constructed this way, students $1, 2, 3, 4$ would choose $1, 2, 3, 3$ respectively. At this point, for student $5$, sessions $1$ and $3$ are both full, so they cannot choose any course.