Problem Description

Takahashi's supermarket has a display shelf. This shelf has $ N $ rows where products can be placed, each row numbered from $1, 2, \ldots, N$. In row $ i $, there are $ K_i $ products placed from front to back, and the expiration date of the $ j $-th product from the front is $ T_{i,j} $.

It is guaranteed that all products have different expiration dates.

$ M $ customers will come in sequence. The $ i $-th customer will look at the first $ a_i $ products from the front in all rows, then choose the product with the highest expiration date value among the viewed products, take it from the shelf, and purchase it.

For each customer, find the expiration date value of the product they purchased.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K_1 $ $ T_{1,1} $ $ T_{1,2} $ $\cdots$ $ T_{1,K_1} $ $\vdots$ $ K_N $ $ T_{N,1} $ $ T_{N,2} $ $\cdots$ $ T_{N,K_N} $ $ M $ $ a_1 $ $ a_2 $ $\cdots$ $ a_M $

Output Format

Output $ M $ lines. The $ i $-th line should contain the expiration date value of the product purchased by the $ i $-th customer.

Sample Input and Output

Sample Input #1

2
3 1 200 1000
5 20 30 40 50 2
5
1 1 1 2 2

Sample Output #1

20
30
40
200
1000

Sample Input #2

10
6 8 24 47 29 73 13
1 4
5 72 15 68 49 16
5 65 20 93 64 91
6 100 88 63 50 90 44
2 6 1
10 14 2 76 28 21 78 43 11 97 70
5 31 9 62 84 40
8 10 46 96 23 98 19 38 51
2 37 77
20
1 1 1 1 2 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1

Sample Output #2

100
88
72
65
93
77
68
63
50
90
64
91
49
46
44
96
37
31
62
20

Notes/Hints

Notes

Discussion about this problem is prohibited until 2020/6/6 18:00 JST. If mentioned, there might be a claim for compensation. It's okay to publish the total score or certification level after the exam, but please do not disseminate information about which problems were solved.

Constraints

• All given inputs are integers.
• $1 \leq N \leq 10^5$
• $1 \leq K_i \leq 10^5$
• $1 \leq M \leq \sum_{i=1}^{N}K_i \leq 3 \times 10^5$
• $1 \leq T_{i,j} \leq 10^9$
• $ T_{i,j} $ are distinct.
• $1 \leq a_i \leq 2$

Sample Explanation 1

• Currently, the expiration dates of the products at the front of the shelf are $ 1 $ in row $ 1 $ and $ 20 $ in row $ 2 $. The customer who came first purchases the product with the value $ 20 $.
• Currently, the expiration dates of the products at the front of the shelf are $ 1 $ in row $ 1 $ and $ 30 $ in row $ 2 $. The second customer purchases the product with the value $ 30 $.
• Currently, the expiration dates of the products at the front of the shelf are $ 1 $ in row $ 1 $ and $ 40 $ in row $ 2 $. The third customer purchases the product with the value $ 40 $.
• Currently, the expiration dates of the products at the front of the shelf are $ 1 $ in row $ 1 $ and $ 50 $ in row $ 2 $. The expiration dates of the products at the second position from the front are $ 200 $ in row $ 1 $ and $ 2 $ in row $ 2 $. The fourth customer purchases the product with the value $ 200 $.
• Currently, the expiration dates of the products at the front of the shelf are $ 1 $ in row $ 1 $ and $ 50 $ in row $ 2 $. The expiration dates of the products at the second position from the front are $ 1000 $ in row $ 1 $ and $ 2 $ in row $ 2 $. The fifth customer purchases the product with the value $ 1000 $.

见题面 Input 部分

见题面 Output 部分