题目描述

欢迎来到神奇的世界！这里有各种令人着迷的神秘配方等待着你探索。你将接受一项重要任务：根据给定的配方和需求，计算所需的原材料数量。

现在，我们有 $n$ 个配方和 $m$ 种原材料。每个配方都有一个唯一的编号（从 $1$ 到 $n$），而原材料的编号从 $n+1$ 到 $n+m$。配方的制作可能需要其他配方作为中间产物，也可能直接需要原材料，但保证不存在循环依赖（即依赖关系构成有向无环图）。

对于第 $i$ 个配方，它会依赖 $k_i$ 个成分。每个成分由编号 $x_j$ 和需求数量 $y_j$ 描述。编号 $x_j$ 可以是其他配方（$x_j \le n$），也可以是原材料（$n+1 \le x_j \le n+m$）。

现在，你需要根据给定的配方依赖关系和数量需求，计算出制作 $q$ 个指定配方（可能重复）所需的每种原材料的数量。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示配方的数量和原材料的数量。

接下来的 $n$ 行，每行描述一个配方。第 $i$ 行的第一个正整数 $k_i$ 表示该配方依赖的成分数量，随后是 $k_i$ 对正整数 $x_j$ 和 $y_j$，表示需要编号为 $x_j$ 的成分 $y_j$ 个。保证同一配方中 $x_j$ 互不相同。

接下来一行包含一个正整数 $q$，表示需要制作的配方总数。

接下来的 $q$ 行，每行包含一个正整数，表示需要制作的一个配方的编号。

输出格式

输出共 $m$ 行，每行一个整数，第 $i$ 行表示制作上述 $q$ 个配方所需要的第 $i$ 种原材料（编号为 $n+i$）的总数量。

样例

2 3
2 2 1 3 2
2 4 2 5 1
3
1
1
2

4
6
3

样例解释

• 配方 $1$ 依赖于 $1$ 个配方 $2$ 和 $2$ 个原材料 $3$。
• 配方 $2$ 依赖于 $2$ 个原材料 $4$ 和 $1$ 个原材料 $5$。

现在需要制作两个配方 $1$ 和一个配方 $2$：

• 原材料 $3$ 的需求量：$2 \times 2 = 4$。
• 原材料 $4$ 的需求量：$2 \times 2 + 2 = 6$（两个配方 $1$ 各需要 $2$ 个配方 $2$，每个配方 $2$ 需要 $2$ 个原材料 $4$；单独的一个配方 $2$ 需要 $2$ 个原材料 $4$）。
• 原材料 $5$ 的需求量：$2 \times 1 + 1 = 3$。

数据范围与提示

• 对于 $20\%$ 的数据：$n \le 100$，$m \le 100$。
• 对于另外 $20\%$ 的数据：$m \le 1$。
• 对于另外 $20\%$ 的数据：配方仅依赖于原材料。
• 对于 $100\%$ 的数据：$n \le 10^5$，$m \le 10^5$，$\sum k_i \le \min(n \times (n+m), 5 \times 10^5)$，$y_j \le 5$，$q \le 10^5$。

所有答案在 $64$ 位整数范围内。