We know that for any regular language

over alphabet

$,$ the complement

is also a regular language. Thus by definition,

has a corresponding finite automaton that accepts it$.$

Write a program that takes as input the description of an NFA $($nondeterministic finite automaton$)$

which accepts language

and produces an NFA

such that

$.$

$\backslash$includegraphics$[$width$=0\mathrm{.}5\backslash$textwidth $]\{1.$png$\}$

Figure $1$: Illustration of the input $($top$)$ and answer $($bottom$)$ for the first test case. Other answers are possible.

Input

The description of the NFA

begins with a line containing an integer

$,$ indicating the number of states in the NFA. States are numbered

through

$.$ State

is the start state. The next line contains an integer

indicating the number of transitions that follow, one transitions per line. Each transition is given as three tokens

where

are the source and destination states, and

is either $$eps$($indicating an epsilon transition$)$ or a single lowercase character $($a$$z$)$ indicating the symbol for that transition. All transitions are unique. At least one transition will have a symbol $($i$.$e$.$ at least one is not an epsilon transition$).$ Following the transitions is an integer

indicating the number of final states. The next

lines contain

unique integers indicating which of the states are final. All listed final states are in the range

to

$.$

Output

Output an NFA

which recognizes exactly the complement of the language recognized by

$,$ using the same format. The alphabet

used to compute the complement is considered to be all the symbols that appear in any part of the definition of

$.$