Problem C
NFA Simulator

Simulate a nondeterministic finite automaton (NFA) on a list of strings to find out whether the NFA accepts or rejects each string.

Figure 1: Illustration of the NFA for the first test case.

An NFA is defined by:

• A set of states $Q$.

• One state $q_0 \in Q$ which is the start state. In this problem, the start state is always numbered $0$.

• An alphabet of symbols $\Sigma $. In this problem, the alphabet is given implicitly (the set of symbols used in the NFA description).

• A set of transitions $Q \times \Sigma _{\varepsilon } \longrightarrow \mathcal{P}(Q)$. Here $\Sigma _{\varepsilon }$ means that a transition may use a symbol from the alphabet $\Sigma $, or it may be an epsilon transition ($\varepsilon $ is not a symbol, but the lack of a symbol). $\mathcal{P}(Q)$ is the powerset of $Q$.

• A set of final states $F \subseteq Q$.

To decide whether the NFA $N$ accepts or rejects a string $w$, it processes one symbol of the string at a time. $N$ maintains a set of current states $C$. Initially $C$ contains the epsilon expansion of the start state $q_0$. (Epsilon expansion takes a set of states and adds all other states that can be reached using only epsilon transitions.) Then for each symbol $w_i \in w$, it performs the following two steps:

• Identify the set of states $C'$ that are reachable from any state in $C$ using a single transition on the symbol $w_i$.

• Let $C$ be the epsilon expansion of $C'$.

Finally, if $C \bigcap F$ is not empty, then $N$ accepts $w$; otherwise $N$ rejects $w$.

Input

Input consists of two parts. The first part describes the NFA. The second part is a list of strings.

The NFA description begins with a line containing an integer $1 \le n \le 100$, indicating the number of states in the NFA. States are numbered $0$ through $n-1$. State $0$ is the start state. The next line contains an integer $0 \le m \le 27 n^2$ indicating the number of transitions that follow, one transition per line. Each transition is given as three tokens $a~ b~ c$ where $0 \le a, c < n$ are the source and destination states, and $b$ is either ‘eps’ (indicating an epsilon transition) or a single lowercase character (a–z) indicating the symbol for that transition. All transitions are unique. Following the transitions is an integer $0 \le f \le n$ indicating the number of final states. The next $f$ lines contain $f$ unique integers indicating which of the states are final. All listed final states are in the range $0$ to $n-1$.

The list of strings starts with an integer $1 \le s \le 100$ indicating the number of lines that follow. Each of the next $s$ lines contains a string (possibly empty) of up to $100$ lowercase English characters (a–z).

Output

For each of the $s$ strings, output ‘accept’ if the NFA would accept the string, or ‘reject’ otherwise.

Scoring

Your program will be tested on a set of test groups, each of which is worth a number of points. Each test group contains several test cases, and to receive the points for a test group your program must solve all of the test cases in that group. The score of your program is the sum of the points received on all of the test groups.

3
3
0 a 1
1 a 2
2 a 2
1
2
3
a
aa
aaaaa

reject
accept
accept

4
5
0 a 0
0 b 0
0 a 1
1 b 2
2 a 3
1
3
7
aba
bab
baba
aaabaaaaa
bbbbbbbbbb
aaaaaaaaa
aaaaaabbbbaba

accept
reject
accept
reject
reject
reject
accept

4
8
0 a 0
0 b 0
0 a 1
0 b 2
1 a 3
2 b 3
3 a 3
3 b 3
1
3
7
aa
bb
abababababab
babababababa
bababaababab
babababbabab
aaaaabbbbb

accept
accept
reject
reject
accept
accept
accept

4
5
0 a 1
1 a 1
0 a 2
2 b 3
3 a 2
3
0
1
3
6

a
aaaaa
abababab
abababa
aab

accept
accept
accept
accept
reject
reject

3
3
0 a 1
1 eps 0
1 eps 2
1
2
5

a
b
aaaaa
aaaaab

reject
accept
reject
accept
reject