Background

Luogu’s testdata is for non-official communication only, and is not official testdata. Official judging link: https://www.cspro.org/.

Xixi Aifu Island Operations Company is a large enterprise responsible for maintaining and operating the island’s infrastructure, with thousands of employees. There are many IT systems in the company. In order to achieve unified authenticated login for these IT systems, the company’s IT department decided to introduce an LDAP system to manage user information within the company. Lightweight Directory Access Protocol (LDAP) is an application-layer protocol used to access and maintain directory services. Its database can organize and store data in a tree structure. Each record contains a unique identifier (DN, Distinguished Name) and a series of attributes (Attribute).

Different IT systems allow different users to access them. Each information system has an expression that describes which users are allowed to access it. This expression can match users using the value of a certain attribute as a condition, or match users using a logical combination of multiple conditions. Little C is assigned to implement such an algorithm: given an IT system’s matching expression, find the DNs of all users that match it.

Problem Description

To simplify the problem, we agree that each user’s DN is a positive integer and is unique. There are several types of user attributes, indexed by positive integers. Each user may have some of these attributes, and each attribute can have only one value. Each attribute value is also a positive integer. For example, suppose there are two users: user $1$ and user $2$, whose DNs are $1$ and $2$, respectively. There are $3$ types of attributes in total. User $1$ has attribute $1$ and attribute $2$, where the value of attribute $1$ is $2$ and the value of attribute $2$ is $3$, but does not have attribute $3$. User $2$ has attribute $2$ and attribute $3$, where the value of attribute $2$ is $3$ and the value of attribute $3$ is $1$, but does not have attribute $1$. The table is as follows:

A matching expression can be an attribute value check, or a logical combination of multiple matching expressions. An expression that matches only one attribute value is called an atomic expression. The form of an atomic expression is <attribute_id><operator><attribute_value>. There are two operators: assertion and anti-assertion. The assertion operator is :, meaning it matches users who have this attribute and whose value equals it. The anti-assertion operator is ~, meaning it matches users who have this attribute and whose value is not equal to it. For example, the expression 1:2 matches user $1$ in the example above, but does not match user $2$. The expression 3~1 matches neither user.

Expressions can be combined logically with the following syntax: <operator>(expr 1)(expr 2). There are two logical operators: AND (&) and OR (|). If the operator is AND, then the expression matches a user if and only if both sub-expressions match that user. If the operator is OR, then the expression matches a user if and only if at least one of the two sub-expressions matches that user. For example, the expression &(1:2)(2:3) matches user $1$ but does not match user $2. The expression |(1:2)(3:1)` matches both users.

Formally, the above syntax in BNF notation is:

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 ")")

Input Format

Read input from standard input.

The first line contains a positive integer $n$, the number of users.

The next $n$ lines each contain several positive integers separated by spaces. The first integer is the user’s DN, the second integer is the number of attributes the user has, and each subsequent pair of integers describes one attribute the user has and its value. These attributes are given in increasing order of attribute id.

The next line contains a positive integer $m$, the number of matching expressions.

The next $m$ lines each contain one matching expression.

Output Format

Write output to standard output.

Output $m$ lines. Each line contains zero or more positive integers separated by spaces, representing the DNs of users that match the corresponding expression, sorted in increasing order.

2
1 2 1 2 2 3
2 2 2 3 3 1
4
1:2
3~1
&(1:2)(2:3)
|(1:2)(3:1)

1

1
1 2

Hint

Sample 1 Explanation

This input group is the example in the problem description.

Subtasks

For $20\%$ of the input, $1 \le n \le 100$, $1 \le m \le 10$, each user has at most $10$ attributes, all attribute ids are at most $100$, and the expressions are atomic expressions, i.e., they satisfy the BNF syntax BASE_EXPR.

For $40\%$ of the input, $1 \le m \le 100$, each user has at most $10$ attributes, all attribute ids are at most $100$, and each expression contains at most a logical combination of two atomic expressions, i.e., it satisfies the BNF syntax EASY_EXPR.

For $70\%$ of the input, all attribute ids are at most $500$.

For all inputs, $1 \le n \le 2500$, $1 \le m \le 500$, each user has at most $500$ attributes, all attribute ids, attribute values, and DNs are at most $10^9$, every expression statement conforms to the given syntax, and the length of each expression string is at most $2000$.

Translated by ChatGPT 5