P16696 [CSPro 29] LDAP

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。 西西艾弗岛运营公司是一家负责维护和运营岛上基础设施的大型企业，拥有数千名员工。公司内有很多 IT 系统。为了能够实现这些 IT 系统的统一认证登录，公司 IT 部门决定引入一套 LDAP 系统来管理公司内的用户信息。轻型目录访问协议（Lightweight Directory Access Protocol, LDAP）是一种用于访问和维护目录服务的应用层协议，基于它的数据库可以用树形结构来组织和存储数据。每一笔数据，都包含了一个唯一的标识符（DN, Distinguished Name），以及一系列的属性（Attribute）。 不同的 IT 系统，允许访问的用户是不相同的。每个信息系统都有一个表达式，用来描述允许访问的用户。这个表达式可以按照某一个属性的值作为条件来匹配用户，也可以用多个条件的逻辑组合来匹配用户。小 C 被安排来实现这样一个算法，给定一个 IT 系统的匹配表达式，找到所有与之匹配的用户的 DN。

为了简化该问题，我们约定，每个用户的 DN 是一个正整数，且不会重复。有若干种用户的属性，用正整数编号。每个用户可以具有这些属性中的若干个，且每个属性只能有一个值。每个属性的值也是一个正整数。例如，假定有两个用户：用户 $1$ 和用户 $2$，他们的 DN 分别是 $1$ 和 $2$。一共有 $3$ 种属性。用户 $1$ 具有属性 $1$ 和属性 $2$，且属性 $1$ 的值为 $2$，属性 $2$ 的值为 $3$；但不具有属性 $3$。用户 $2$ 具有属性 $2$ 和属性 $3$，且属性 $2$ 的值为 $3$，属性 $3$ 的值为 $1$；但不具有属性 $1$。如下表所示： | **DN** | **属性 1** | **属性 2** | **属性 3** | |:------:|:----------:|:----------:|:----------:| | 1 | 2 | 3 | N/A | | 2 | N/A | 3 | 1 | 一个匹配表达式可以是一个属性的值，也可以是多个匹配表达式的逻辑组合。只匹配一个属性的值的表达式称为原子表达式，原子表达式的形式为 ``。其中操作符有两种：断言与反断言。断言操作符为 `:`，表示匹配具有该属性且值与之相等的用户；反断言操作符为 `~`，表示匹配具有该属性且值与之不等的用户。例如，表达式 `1:2` 可以与上述用户 $1$ 相匹配，但不能与用户 $2$ 相匹配；而表达式 `3~1` 则不能与任何一个用户相匹配。 表达式可以进行逻辑组合，其语法是：`(表达式 1)(表达式 2)`。其中操作符有两种：与（`&`）和或（`|`）。如果操作符为与，则当且仅当两个表达式都与某一用户相匹配时，该表达式与该用户相匹配；如果操作符为或，则当且仅当两个表达式中至少有一个与某一用户相匹配时，该表达式与该用户相匹配。例如，表达式 `&(1:2)(2:3)` 可以与用户 $1$ 相匹配，但不能与用户 $2$ 相匹配；而表达式 `|(1:2)(3:1)` 则可以与两个用户都相匹配。 形式化地，上述语法用 BNF 范式表示如下： ``` NON_ZERO_DIGIT = "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" DIGIT = "0" / NON_ZERO_DIGIT NUMBER = NON_ZERO_DIGIT / (NON_ZERO_DIGIT DIGIT*) ATTRIBUTE = NUMBER VALUE = NUMBER OPERATOR = ":" / "~" BASE_EXPR = ATTRIBUTE OPERATOR VALUE LOGIC = "&" / "|" EXPR = BASE_EXPR / (LOGIC "(" EXPR ")" "(" EXPR ")") EASY_EXPR = BASE_EXPR / (LOGIC "(" BASE_EXPR ")" "(" BASE_EXPR ")") ```

从标准输入读入数据。 输入的第一行包含一个正整数 $n$，表示用户的数目。 接下来 $n$ 行，每行包含空格分隔的若干个正整数，第一个正整数表示该用户的 DN，第二个正整数表示该用户具有的属性个数，此后的每两个正整数表示该用户具有的一个属性及其值。这些属性按照属性编号从小到大的顺序给出。 接下来一行包含一个正整数 $m$，表示匹配表达式的数目。 接下来 $m$ 行，每行包含一个匹配表达式。

输出到标准输出。 输出 $m$ 行，每行包含零个或多个正整数，用空格分隔，表示与对应的匹配表达式相匹配的用户的 DN，由小到大排序。

### 样例 1 解释 本组输入是题目描述中的例子。 ### 子任务 对于 $20\%$ 的输入，有 $1 \le n \le 100$，$1 \le m \le 10$，每个用户的属性个数不超过 $10$，全部属性编号不超过 $100$，且表达式是原子表达式，即符合 BNF 语法 `BASE_EXPR`。 对于 $40\%$ 的输入，有 $1 \le m \le 100$，每个用户的属性个数不超过 $10$，全部属性编号不超过 $100$，且表达式中至多含有两个原子表达式的逻辑组合，即符合 BNF 语法 `EASY_EXPR`。 对于 $70\%$ 的输入，有全部属性编号不超过 $500$。 对于全部输入，有 $1 \le n \le 2500$，$1 \le m \le 500$，每个用户的属性个数不超过 $500$，全部属性编号、属性值和 DN 均不超过 $10^9$，每个表达式语句都符合题设语法，且语句字符长度不超过 $2000$。