Університетська Промоція

Вхідні дані

Перший рядок містить одне ціле число $t$ (1 \le t \le 10^4) — кількість наборів входних даних.

Перший рядок кожного набору входних даних містить два цілі числа $n$ та $m$ (1 \le n \le 2 \times 10^5,\; 1 \le m \le 50) — кількість студентів та кількість спеціальностей.

Другий рядок кожного набору входних даних містить $n$ цілих чисел a_1, a_2, \dots, a_n (0 \le a_i \le 10^9) — оцінки студентів. Оцінки не гарантуються як різні.

Наступні $n$ рядків описують переваги кожного студента. Кожен з цих рядків починається з цілого числа k_i (1 \le k_i \le m) слідом за яким йдуть k_i цілих чисел: p_{i1}, p_{i2}, \dots, p_{ik_i} (1 \le p_{ij} \le m) — де p_{ij} є $j$-ю бажаною спеціальністю студента $i$.

Наступний рядок містить $m$ цілих чисел b_1, b_2, \dots, b_m (0 \le b_j \le 10^9) — мінімально необхідна оцінка для кожної спеціальності.

Наступний рядок містить $m$ цілих чисел c_1, c_2, \dots, c_m (0 \le c_j \le 10^9) — кількість доступних місць для кожної спеціальності.

Гарантується, що \sum n \le 2 \times 10^5.

Гарантується, що \sum k_i \le 5 \times 10^6.

Гарантується, що значення p_{ij} є парно різними для кожного студента.

Вихідні дані

Виведіть масив d_1,d_2,...,d_n, де d_i — це остаточна спеціальність, призначена студенту $i$, або $-1$, якщо студент не прийнятий на жодну спеціальність.

Приклади

Примітка

У першому наборі даних:

1. Студент $1$ (Оцінка $90$): Переваги \{1, 2, 3\}. Спеціальність $1$ вимагає $>80$ ($90$ підходить) і має $1$ місце.

   Результат: Спеціальність $1$ $(0$ місць залишилося $)$ .

   Студент $2$ (Оцінка $85$): Переваги $\{1,2\}$. Спеціальність $1$ заповнена. Спеціальність $2$ вимагає $>80$ ($85$ підходить) і має $1$ місце.

   Результат: Спеціальність $2$ $(0$ місць залишилося $)$.

2. Студент $3$ (Оцінка $85$): Переваги \{2, 3, 4\}. Спеціальність $2$ заповнена. Спеціальність $3$ вимагає $>60$ ($85$ підходить) і має 2 місця.

   Результат: Спеціальність $3$ $(1$ місце залишилося $)$.

3. Студент $4$ (Оцінка $70$): Переваги $\{1\}$. Спеціальність $1$ заповнена і 70 \ngtr 80.

   Результат: $-1$.

4. Студент $5$ (Оцінка $60$): Переваги $\{3,4\}$. Спеціальність $3$ вимагає $>60$ ($60$ не є $>60$). Спеціальність $4$ вимагає $>40$ ($60$ підходить) і має $1$ місце.

   Результат: Спеціальність $4$ $(0$ місць залишилося $)$ .

5. Студент $6$ (Оцінка $50$): Переваги $\{4\}$. Спеціальність $4$ заповнена.

   Результат: $-1$.

Оцінювання

1. Підзадача $1$ ($30$ балів) : (1 \le \sum n \le 3000)

2. Підзадача $2$ ($120$ балів) : Без додаткових обмежень