← 返回题目列表

Codeforces · 1765/L

L. 项目经理

中文机器翻译题面 查看原题

Bersoft 公司共有 $$$n$$$ 名员工,编号从 $$$1$$$ 到 $$$n$$$。每个员工在一周中的某些日子工作,在其他日子休息。您将获得每位员工每周的工作日列表。

有正常工作日和节假日。在正常日子里,只有那些在清单上列出了一周中的当天的员工才工作。节假日,没人上班。您将获得假期列表。天数从 $$$1$$$ 开始编号,$$$1$$$ 是星期一。

公司收到了必须完成的 $$$k$$$ 项目报价。项目按优先级降序编号,从 $$$1$$$ 到 $$$k$$$。

每个项目由多个部分组成,其中第 $$$i$$$ 部分必须由第 $$$a_i$$$ 员工完成。这些部分必须按顺序完成(即第 $$$(i+1)$$$-st 部分只能在第 $$$i$$$-th 部分完成后才能开始)。每个部分都需要相应的员工一天才能完成。

这些项目可以同时进行。然而,一名员工一天内只能完成一个项目的一部分。如果他们可以选择完成哪个项目的一部分,他们总是会选择优先级最高(指数最低)的项目。

对于每个项目,输出项目完成的日期。

输入

The first line contains three integers $$$n, m$$$ and $$$k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^5$$$) — the number of employees, the number of holidays and the number of projects.

接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含第 $$$i$$$ 员工的工作日列表。首先,单个整数 $$$t$$$ ($$$1 \le t \le 7$$$) — 工作日数。然后按升序排列一周中的 $$$t$$$ 天。可能的日期是:“星期一”、“星期二”、“星期三”、“星期四”、“星期五”、“星期六”、“星期日”。

下一行包含 $$$m$$$ 整数 $$$h_1, h_2, \dots, h_m$$$ ($$$1 \le h_1 < h_2 < \dots < h_m \le 10^9$$$) — 假期列表。

接下来的 $$$k$$$ 行中的第 $$$j$$$ 行包含第 $$$j$$$ 项目的描述。它以整数 $$$p$$$ 开头 ($$$1 \le p \le 2 \cdot 10^5$$$) — 项目中的部件数量。 Then $$$p$$$ integers $$$a_1, a_2, \dots, a_p$$$ ($$$1 \le a_x \le n$$$) follow, where $$$p_i$$$ is the index of the employee that must complete the $$$i$$$-th part.

所有项目中的零件总数不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$k$$$ 整数 - 第 $$$j$$$ 个值应等于第 $$$j$$$ 个项目完成的日期。

示例

输入 #1

3 5 4
2 Saturday Sunday
2 Tuesday Thursday
4 Monday Wednesday Friday Saturday
4 7 13 14 15
5 1 1 3 3 2
3 2 3 2
5 3 3 3 1 1
8 3 3 3 3 3 3 3 3

输出 #1

25 9 27 27