P13912 [CSPro 26] 角色授权

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。 为了响应国家发展新基建的倡议，西西艾弗岛上兴建了西西艾弗数据中心，并以此为基础运营了西西艾弗云。作为数据中心的运营和维护方， 西西艾弗云公司十分重视西西艾弗云的网络安全管理工作。众所周知，安全性和便捷性难以兼得，同时， 一个混乱的权限模型可能会导致人员被授予不必要的权限，从而造成安全风险。因此在西西艾弗云公司的网络安全部工作的小 C 专门设计了一种科学的权限模型。 这种安全模型将验证流程分为两个步骤。第一步是验证用户的身份（鉴别），第二步是验证用户的权限（授权）。在第一步， 首先验证一个用户是否是该用户所声称的那个身份。例如，通过验证用户提供的口令（Password）是否正确，或者通过验证用户提供的智能卡是否合法有效。 接下来，在授权的步骤中，权限策略会被检索以便判断来访的用户是否能够操作系统中的某个资源。 为了能够灵活地表达用户和授权之间的关系，西西艾弗云公司设计了一种简洁而灵活的授权模型：基于角色的授权模型。它的思路是：首先设定若干角色， 每个角色中指明了一个清单，表明允许访问的资源的种类、资源的名称和对资源的操作；然后将被前一步骤已经鉴别过的用户和一个或多个角色相关联。 某个用户能够执行的操作，即为与其关联的全部角色中允许的操作的并集。 小 C 将实现授权模型的工作交给了你，希望你能够把它们实现出来。

用户表示授权模型中的一个已识别的主体，该识别过程由此前的鉴别过程完成。一个用户具有下列要素： - 名称：是一个字符串，用于唯一标识一个用户； - 用户组：是一个数组，包含若干个字符串，表示该用户所属的用户组。 一个待授权的行为，包括下列要素： - 主体：是一个用户，包括试图进行该行为的用户的名称和该用户所属的用户组； - 操作：是一个字符串，一般是一个动词，例如 $\text{Read}$、$\text{Open}$、$\text{Close}$ 等； - 资源：表示该行为的操作对象，由资源种类和资源名称描述。资源种类例如 $\text{Door}$、$\text{File}$ 等；在一个特定的资源种类中，资源名称唯一确定了一个资源。 需要注意的是，一个待授权的行为的主体信息，即用户名称和所属用户组，是由前一步骤的鉴别过程完成的。因此，每次授权过程中，每个待授权的行为都会包含主体用户和其关联的用户组的信息。由于鉴权过程中的其它因素，同一个名称的用户在先后两次待授权的行为中所属的用户组可能有区别，不能存储或记忆此前每个待授权的行为中，用户与用户组的关联情况，而是要按照每次待授权的行为中给出的信息独立判断。 角色是这种授权模型的基本单位，它指明了一个用户可以执行的操作，角色的清单中描述了角色所允许的操作。一个角色包含下列要素： - 名称，是一个字符串，用于唯一标识一个角色； - 操作清单，是一个数组，包含一个或多个操作，表示该角色允许执行的操作集合； - 资源种类清单，是一个数组，包含一个或多个资源种类，表示该角色允许操作的资源的种类集合； - 资源名称清单，是一个数组，包含若干个资源名称，表示该角色允许操作的资源的名称集合。 判断一个角色能否对某个资源执行某个操作的过程是： 1. 检查该角色的操作清单，如果该角色的操作清单中不包含该操作，且该角色的操作清单中也不包含字符串 $\text{*}$，那么不能执行该操作； 2. 检查该角色的资源种类清单，如果该角色的资源种类清单中不包含该资源的种类，且该角色的资源种类清单中也不包含字符串 $\text{*}$，那么不能执行该操作； 3. 检查该角色的资源名称清单，如果该角色的资源名称清单中不包含该资源的名称，且该角色的资源名称清单不是空数组，那么不能执行该操作； 4. 允许执行该操作。 例如，假设有某个角色 $\text{Doorman}$，其允许执行的操作有 $\text{Open}$ 和 $\text{Close}$，其允许操作的资源类型有 $\text{Door}$，其允许操作的资源名称有 $\text{FrontDoor}$ 和 $\text{BackDoor}$。如果某用户与这个角色关联，那么该用户可以对名为 $\text{FrontDoor}$ 的 $\text{Door}$ 执行 $\text{Open}$ 操作，但是不能对 $\text{BackDoor}$ 的 $\text{Door}$ 执行 $\text{Delete}$ 操作。同时，一个角色能允许进行的操作可以用通配符来表示。例如，另一个角色 $\text{Admin}$，其允许执行的操作有 $*$，允许操作的资源类型是 $*$，其允许操作的资源名称列表为空，那么与该角色关联的所有用户可以执行任何操作。值得注意的是，一个角色的操作清单，只能用允许列表的方式列举该角色允许进行的操作，而不能禁止角色进行某个操作。 角色关联指明了一个用户和一个或多个角色之间的关系。一个角色关联包含下列要素： - 角色名称，是一个字符串，用于指明一个角色； - 授权对象清单，是一个数组，包含一个或多个用户名称或者用户组名称，表示该角色关联的用户和用户组的集合。 判断一个用户能否执行某个操作的过程是： 1. 检查所有的角色关联的授权对象清单，如果清单中包含该用户的名称，或者该清单中包含该用户所属的某一个用户组的名称，那么选取该角色关联所关联的角色； 2. 对于所有被选取的角色，判断这些角色是否能对该资源执行该操作，如果所有角色都不能执行该操作，那么不能执行该操作； 3. 允许执行该操作。 由此可见，一个角色关联可以将一个角色与多个用户或用户组关联起来。例如，如果有一个角色关联，其关联的角色名称为 $\text{Doorman}$，其关联的用户和用户组清单为用户 $\text{foo1}$、用户 $\text{foo2}$、用户组 $\text{bar}$。那么这些用户会与 $\text{Doorman}$ 角色关联： - 名为 $\text{foo1}$ 的用户，属于用户组 $\text{bar}$； - 名为 $\text{foo2}$ 的用户，属于用户组 $\text{barz}$； - 名为 $\text{foo3}$ 的用户，属于用户组 $\text{bar}$ 和 $\text{barz}$。 但是，属于用户组 $\text{barz}$ 的名为 $\text{foo4}$ 的用户不能与 $\text{Doorman}$ 的角色关联。 从上述判断规则可以知道，一个用户可能与多个角色相关联，在这种情况下，该用户允许进行的操作是这些角色被允许进行的操作集合的**并集**。

从标准输入读入数据。 输入的第一行包含三个正整数 $n$、$m$、$q$，分别表示角色数量、角色关联数量和待检查的操作数量。 输入接下来的 $n$ 行中，每行表示一个角色，包括空格分隔的若干元素，依次为： - 一个字符串，表示该角色的名称； - 一个正整数 $nv$，表示操作清单中包含的操作数量； - $nv$ 个字符串，依次表示操作清单中的操作； - 一个正整数 $no$，表示资源种类清单中包含的资源种类的数量； - $no$ 个字符串，依次表示资源种类清单中的资源种类； - 一个非负整数 $nn$，表示资源名称清单中包含的资源名称的数量； - $nn$ 个字符串，依次表示资源名称清单中的资源名称。 输入接下来的 $m$ 行中，每行表示一个角色关联，包括空格分隔的若干元素，依次为： - 一个字符串，表示该角色关联的角色名称； - 一个正整数 $ns$，表示授权对象清单中包含的授权对象的数量； - $2ns$ 个字符串，每两个表示授权对象清单中的授权对象，前一个字符串为 $\text{u}$ 或 $\text{g}$，分别表示这个授权对象是一个用户名称或者用户组名称，后一个字符串为用户名称或者用户组名称。 输入接下来的 $q$ 行中，每行表示一个待授权的行为，包括空格分隔的若干元素，依次为： - 一个字符串，表示执行该操作的用户名称； - 一个正整数 $ng$，表示该用户所属的用户组的数量； - $ng$ 个字符串，依次表示该用户所属的用户组的名称； - 一个字符串，表示待查操作的名称； - 一个字符串，表示被操作的资源种类； - 一个字符串，表示被操作的资源名称。

输出到标准输出。 输出 $q$ 行，每行表示一个操作是否可以被执行，$\text{0}$ 表示不能执行，$\text{1}$ 表示可以执行。

### 样例解释 在本例中，定义了一个名为 $\text{op}$ 的角色，授予了对任意 $\text{door}$ 类型的对象的 $\text{open}$ 操作的权限，同时定义了两个指向 $\text{op}$ 的角色关联。注意，可以针对一个角色定义多于一个角色关联。本例给出了三个待授权的行为。其中，第一个行为，授权的主体用户是 $\text{xiaoc}$，该用户所属的用户组 $\text{sre}$ 被关联 $\text{op}$ 角色，因此可以执行开门动作。第二个行为中，授权的主体用户是 $\text{xiaop}$，该用户被直接关联了 $\text{op}$ 角色，因此也可以执行开门动作。第三个行为中，授权的主体用户仍是 $\text{xiaoc}$，关联的角色仍为 $\text{op}$。但是，由于 $\text{op}$ 角色并未被授予 $\text{remove}$ 操作的权限，因此该动作被拒绝。 ### 子任务 对于 $20\%$ 的数据，有 $n = m = 1$，且给出的角色类似于题目正文中用于举例的 $\text{Admin}$，允许执行任何操作，且 $nv = no = ns = ng = 1$、$nn = 0$。 对于 $40\%$ 的数据，有 $1 \leq n, m \leq 50$，且 $nv = no = ns = 1$、$ng \leq 40$、$nn = 0$。 对于 $70\%$ 的数据，有 $1 \leq n, m \leq 50$，且 $nv, no, ns, ng \leq 40$、$nn \leq 400$。 对于 $100\%$ 的数据，有： - $1 \leq n, m \leq 500$； - $1 \leq q \leq 5000$； - $1 \leq nv, no, ns, ng \leq 400$； - $0 \leq nn \leq 400$； - 全部字符串或为 $\text{*}$，或仅包含大写字母、小写字母、数字（`A-Z`，`a-z`，`0-9`），且字符数目不超过 10。