AT_past202005_l スーパーマーケット

[problemUrl]: https://atcoder.jp/contests/past202005-open/tasks/past202005_l 高橋君のスーパーマーケットには陳列棚があります。 この陳列棚には商品を並べられる列が $ N $ 本あり、それぞれの列には $ 1,2,\ldots,N $ の番号がついています。 列 $ i $ には $ K_i $ 個の商品が手前から奥へと一列に並べられており、手前から $ j $ 番目の商品の消費期限は $ T_{i,j} $ です。 ここで、全ての商品の消費期限は相異なることが保証されます。 $ M $ 人の客が順番にやってきます。 $ i $ 番目にやってきた客は全ての列について現在の時点で手前から $ a_i $ 番目までにある商品を見た後、見た商品のうち最も消費期限の値が大きいものを選んで棚から取って購入します。 それぞれの客について、購入した商品の消費期限の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

$ M $ 行出力せよ。$ i $ 行目では $ i $ 番目にやってきた客が購入した商品の消費期限の値を出力せよ。

### 注意 この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 与えられる入力は全て整数 - $ 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} $ は相異なる - $ 1\ \leq\ a_i\ \leq\ 2 $ ### Sample Explanation 1 \- 現在、棚の $ 1 $ 番手前にある商品の消費期限は列 $ 1 $ が $ 1 $、列 $ 2 $ が $ 20 $ です。これらのうち値が最大である $ 20 $ の商品を $ 1 $ 番目にやってきた客は購入します。 - 現在、棚の $ 1 $ 番手前にある商品の消費期限は列 $ 1 $ が $ 1 $、列 $ 2 $ が $ 30 $ です。これらのうち値が最大である $ 30 $ の商品を $ 2 $ 番目にやってきた客は購入します。 - 現在、棚の $ 1 $ 番手前にある商品の消費期限は列 $ 1 $ が $ 1 $、列 $ 2 $ が $ 40 $ です。これらのうち値が最大である $ 40 $ の商品を $ 3 $ 番目にやってきた客は購入します。 - 現在、棚の $ 1 $ 番手前にある商品の消費期限は列 $ 1 $ が $ 1 $、列 $ 2 $ が $ 50 $ です。棚の $ 2 $ 番目に手前にある商品の消費期限は列 $ 1 $ が $ 200 $、列 $ 2 $ が $ 2 $ です。これらのうち値が最大である $ 200 $ の商品を $ 4 $ 番目にやってきた客は購入します。 - 現在、棚の $ 1 $ 番手前にある商品の消費期限は列 $ 1 $ が $ 1 $、列 $ 2 $ が $ 50 $ です。棚の $ 2 $ 番目に手前にある商品の消費期限は列 $ 1 $ が $ 1000 $、列 $ 2 $ が $ 2 $ です。これらのうち値が最大である $ 1000 $ の商品を $ 5 $ 番目にやってきた客は購入します。