AT_past202005_l スーパーマーケット

一个自动售货机有编号为 $1$ 到 $n$ 的 $n$ 个通道。第 $i$ 个通道内有 $k_i$ 个商品，价值从前往后依次为 $t_{i,1},t_{i,2},...,t_{i,k_i}$。保证所有 $t_{i,j}$ 互不相同。 有 $m$ 位顾客先后使用了这台自动售货机。第 $i$ 个使用的顾客会检查每个通道内最靠前的 $a_i$ 个商品的价值（若少于 $a_i$ 则全部检查），然后选择最大的并买下。请将所有客户买走的产品的价值分别求出。

第一行：一个整数 $n$。 接下来 $n$ 行：第 $i$ 行第 $1$ 个数为 $k_i$，然后是 $k_i$ 个数 $t_{i,1},t_{i,2},...,t_{i,k_i}$。 接下来一行：一个整数 $m$。 接下来一行：$m$ 个整数 $a_1,a_2,...,a_m$。

$m$ 行，第 $i$ 行输出一个正整数，即第 $i$ 名顾客买走的商品的价值。 ### 数据约束条件 - 输入均为整数； - $1 \le n,k_i \le 10^5$； - $1 \le m \le$ 所有 $k_i$ 之和 $\le 3 \times 10^5$； - $1 \le t_{i,j} \le 10^9$； - $1 \le a_i \le 2$。

### 注意 この問題に対する言及は、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 $ 番目にやってきた客は購入します。