Universitet Təşviqi

Giriş

İlk sətirdə bir tam ədəd $t$ (1 \le t \le 10^4) — test hallarının sayı.

Hər test halının ilk sətirində iki tam ədəd $n$ və $m$ (1 \le n \le 2 \times 10^5,\; 1 \le m \le 50) — tələbələrin sayı və ixtisasların sayı.

Hər test halının ikinci sətirində $n$ tam ədəd a_1, a_2, \dots, a_n (0 \le a_i \le 10^9) — tələbələrin balları. Balların fərqli olacağına zəmanət verilmir.

Sonrakı $n$ sətir hər tələbənin üstünlüklərini təsvir edir. Bu sətirlərdən hər biri bir tam ədəd k_i ilə başlayır (1 \le k_i \le m) sonra k_i tam ədəd: p_{i1}, p_{i2}, \dots, p_{ik_i} (1 \le p_{ij} \le m) — burada p_{ij} tələbə $i$-nin $j$-ci üstünlük verdiyi ixtisasdır.

Sonrakı sətir $m$ tam ədəd b_1, b_2, \dots, b_m (0 \le b_j \le 10^9) — hər ixtisas üçün minimum tələb olunan baldır.

Sonrakı sətir $m$ tam ədəd c_1, c_2, \dots, c_m (0 \le c_j \le 10^9) — hər ixtisas üçün mövcud yerlərin sayıdır.

Zəmanət verilir ki, \sum n \le 2 \times 10^5.

Zəmanət verilir ki, \sum k_i \le 5 \times 10^6.

Zəmanət verilir ki, p_{ij} dəyərləri hər tələbə üçün bir-birindən fərqlidir.

Çıxış

Bir massiv d_1,d_2,...,d_n çap edin, burada d_i tələbə $i$-yə təyin olunan son ixtisasdır, ya da tələbə heç bir ixtisasa qəbul edilmədikdə $-1$.

Nümunələr

Qeyd

İlk test halında:

1. Tələbə $1$ (Bal $90$): Üstünlükləri \{1, 2, 3\}. Ixtisas $1$ $>80$ tələb edir ($90$ uyğundur) və $1$ yer var.

   Nəticə: Ixtisas $1$ $(0$ yer qaldı $)$ .

   Tələbə $2$ (Bal $85$): Üstünlükləri $\{1,2\}$. Ixtisas $1$ doludur. Ixtisas $2$ $>80$ tələb edir ($85$ uyğundur) və $1$ yer var.

   Nəticə: Ixtisas $2$ $(0$ yer qaldı $)$.

2. Tələbə $3$ (Bal $85$): Üstünlükləri \{2, 3, 4\}. Ixtisas $2$ doludur. Ixtisas $3$ $>60$ tələb edir ($85$ uyğundur) və $2$ yer var.

   Nəticə: Ixtisas $3$ $(1$ yer qaldı $)$.

3. Tələbə $4$ (Bal $70$): Üstünlük $\{1\}$. Ixtisas $1$ doludur və 70 \ngtr 80.

   Nəticə: $-1$.

4. Tələbə $5$ (Bal $60$): Üstünlükləri $\{3,4\}$. Ixtisas $3$ $>60$ tələb edir ($60$ $>60$ deyil). Ixtisas $4$ $>40$ tələb edir ($60$ uyğundur) və $1$ yer var.

   Nəticə: Ixtisas $4$ $(0$ yer qaldı $)$ .

5. Tələbə $6$ (Bal $50$): Üstünlük $\{4\}$. Ixtisas $4$ doludur.

   Nəticə: $-1$.

Bal hesablama

1. Alt tapşırıq $1$ ($30$ bal) : (1 \le \sum n \le 3000)

2. Alt tapşırıq $2$ ($120$ bal) : Əlavə Məhdudiyyət yoxdur