University Promotion

Input

The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ (1 \le n \le 2 \times 10^5,\; 1 \le m \le 50) — the number of students and the number of majors.

The second line of each test case contains $n$ integers a_1, a_2, \dots, a_n (0 \le a_i \le 10^9) — the scores of the students. Scores are not guaranteed to be distinct.

The next $n$ lines describe the preferences of each student. Each of these lines starts with an integer k_i (1 \le k_i \le m) followed by k_i integers: p_{i1}, p_{i2}, \dots, p_{ik_i} (1 \le p_{ij} \le m) — where p_{ij} is the $j$-th preferred major of student $i$.

The next line contains $m$ integers b_1, b_2, \dots, b_m (0 \le b_j \le 10^9) — the minimum required score for each major.

The next line contains $m$ integers c_1, c_2, \dots, c_m (0 \le c_j \le 10^9) — the number of available seats for each major.

It is guaranteed that the \sum n \le 2 \times 10^5.

It is guaranteed that the \sum k_i \le 5 \times 10^6.

It is guaranteed that the values p_{ij} are pairwise distinct for each student.

Output

Print an array d_1,d_2,...,d_n where d_i is the final major assigned to student $i$, or $-1$ if the student is not admitted to any major.

Examples

Note

In the first test case :

1. Student $1$ (Score $90$): Preferences are \{1, 2, 3\}. Major $1$ requires $>80$ ($90$ is okay) and has $1$ seat.

   Result: Major $1$ $(0$ seats left $)$ .

   Student $2$ (Score $85$): Preferences $\{1,2\}$. Major $1$ is full. Major $2$ requires $>80$ ($85$ is okay) and has $1$ seat.

   Result: Major $2$ $(0$ seats left $)$.

2. Student $3$ (Score $85$): Preferences \{2, 3, 4\}. Major $2$ is full. Major $3$ requires $>60$ ($85$ is okay) and has 2 seats.

   Result: Major $3$ $(1$ seat left $)$.

3. Student $4$ (Score $70$): Preference $\{1\}$. Major $1$ is full and 70 \ngtr 80.

   Result: $-1$.

4. Student 5 (Score 60): Preferences $\{3,4\}$. Major $3$ requires $>60$ ($60$ is not $>60$). Major $4$ requires $>40$ ($60$ is okay) and has $1$ seat.

   Result: Major $4$ $(0$ seats left $)$ .

5. Student $6$ (Score $50$): Preference $\{4\}$. Major $4$ is full.

   Result: $-1$.

Scoring

1. Subtask $1$ ($30$ points) : (1 \le \sum n \le 3000)

2. Subtask $2$ ($120$ points) : No additional Contraints