F - Pharmacist Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 7 点

問題文

1 から N までの番号がついた N 種類の薬があります。
薬の効き目は 1 から 100 までの整数で表されて、大きければ大きいほど効き目が高いです。薬 i の効き目は A_i です。(A_i は全て相異なります。)
また、薬にはアレルゲン(アレルギー反応の原因となる物質)が入っています。アレルゲンは 1 から 2 \times 10^5 までの整数で表せて、薬 i には C_i 個のアレルゲン X_{i,1}, X_{i,2}, \dots, X_{i,C_i} が含まれています。

Q 個のクエリが与えられるので指示に従って処理してください。p 番目のクエリは以下の通りです。

人 p は D_p 種類のアレルギーを持っていて、アレルゲン Y_{p,1}, Y_{p,2}, \dots, Y_{p,D_p} のいずれか 1 つ以上を含んでいる薬を与えることはできません。
人 p に 薬 1 から薬 N のうちいずれか 1 つを与えることを考えます。人 p に与えることができる薬の中で最も効き目の高い薬の番号を出力してください。ただし、与えることができる薬が存在しなければ -1 を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • i \neq j ならば A_i \neq A_j
  • 0 \leq C_i
  • 0 \leq \sum_{i=1}^N C_i \leq 10^5
  • 1 \leq X_{i,j} \leq 2 \times 10^5
  • j \neq k ならば X_{i, j} \neq X_{i, k}
  • 1 \leq Q \leq 10^5
  • 0 \leq D_p
  • 0 \leq \sum_{p=1}^Q D_{p} \leq 10^5
  • 1 \leq Y_{p,q} \leq 2 \times 10^5
  • q \neq r ならば Y_{p,q} \neq Y_{p,r}
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N
C_1
X_{1,1} X_{1,2} \dots X_{1,C_1}
C_2
X_{2,1} X_{2,2} \dots X_{2,C_2}
\vdots
C_N
X_{N,1} X_{N,2} \dots X_{N,C_N}
Q
D_1
Y_{1,1} Y_{1,2} \dots Y_{1,D_1}
D_2
Y_{2,1} Y_{2,2} \dots Y_{2,D_2}
\vdots
D_Q
Y_{Q,1} Y_{Q,2} \dots Y_{Q,D_Q}

出力

Q 行出力せよ。i 行目には i 番目のクエリへの答えを出力せよ。

入力例 1

3
10 9 8
3
1 2 3
1
1
2
2 3
4
0

1
1
1
2
2
1 2

出力例 1

1
3
2
-1

参考として、薬およびクエリに関する情報をまとめると次のようになります。

  • 薬 1 は効き目が 10 でアレルゲン 1,2,3 を含んでいる。
  • 薬 2 は効き目が 9 でアレルゲン 1 を含んでいる。
  • 薬 3 は効き目が 8 でアレルゲン 2,3 を含んでいる。
  • 人 1 にはすべての薬を与えることができる。
  • 人 2 にはアレルゲン 1 の入った薬を与えられない。
  • 人 3 にはアレルゲン 2 の入った薬を与えられない。
  • 人 4 にはアレルゲン 1, 2 の少なくとも一方が入った薬を与えられない。

Score : 7 points

Problem Statement

We have N kinds of drugs numbered 1 to N.
The efficiency of a drug is represented by an integer from 1 to 100; the greater, the more efficient. The efficiency of Drug i is A_i. (All A_i are distinct.)
The drugs also contain allergens (substances that cause allergic reactions). Allergens are represented by integers from 1 to 2 \times 10^5, and Drug i contains C_i allergens X_{i,1}, X_{i,2}, \dots, X_{i,C_i}.

You are given Q queries, which should be processed according to the instruction. The p-th query is the following:

Person p has allergies to D_p allergens Y_{p,1}, Y_{p,2}, \dots, Y_{p,D_p}, and may not be given a drug containing one or more of those allergens.
Consider giving Person p one of the drugs from Drug 1 to Drug N. Print the number representing the most efficient drug that may be given to Person p. If no drug may be given, print -1.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • A_i \neq A_j if i \neq j.
  • 0 \leq C_i
  • 0 \leq \sum_{i=1}^N C_i \leq 10^5
  • 1 \leq X_{i,j} \leq 2 \times 10^5
  • X_{i, j} \neq X_{i, k} if j \neq k.
  • 1 \leq Q \leq 10^5
  • 0 \leq D_p
  • 0 \leq \sum_{p=1}^Q D_{p} \leq 10^5
  • 1 \leq Y_{p,q} \leq 2 \times 10^5
  • Y_{p,q} \neq Y_{p,r} if q \neq r.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
C_1
X_{1,1} X_{1,2} \dots X_{1,C_1}
C_2
X_{2,1} X_{2,2} \dots X_{2,C_2}
\vdots
C_N
X_{N,1} X_{N,2} \dots X_{N,C_N}
Q
D_1
Y_{1,1} Y_{1,2} \dots Y_{1,D_1}
D_2
Y_{2,1} Y_{2,2} \dots Y_{2,D_2}
\vdots
D_Q
Y_{Q,1} Y_{Q,2} \dots Y_{Q,D_Q}

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

3
10 9 8
3
1 2 3
1
1
2
2 3
4
0

1
1
1
2
2
1 2

Sample Output 1

1
3
2
-1

Here is a summary of information about the drugs and queries.

  • Drug 1 has an efficiency of 10 and contains Allergens 1, 2, and 3.
  • Drug 2 has an efficiency of 9 and contains Allergen 1.
  • Drug 3 has an efficiency of 8 and contains Allergens 2 and 3.
  • Person 1 may be given any drug.
  • Person 2 may not be given a drug containing Allergen 1.
  • Person 3 may not be given a drug containing Allergen 2.
  • Person 4 may not be given a drug containing one or more of Allergens 1 and 2.