Suffix machine gun#2765
Either pass or automatic.___________________
Hannibal Rector
Theoretical training for new recruits in the Possiltum army included not only classes in military law but also the basics of cryptography. These lectures were delivered by Major Mega Byte, who was known for his characteristic soldier's humor. Guido and Nunzio, whose task was to undermine the Possiltum army from within, decided to take advantage of this by introducing confusion into the terminology. At the beginning of the next lecture, Nunzio raised his hand and asked:
- In the last lecture, you talked about finite automata. Will you tell us about finite machine guns?
Major Mega Byte was not at a loss.
- A suffix machine gun is a finite automaton that accepts all suffixes of a given string (from the zero-th to the -th inclusive, where is the length of the string), and only them. Sergeant Guido!
- Yes, sir, Major!
- Can you distinguish an automaton from a machine gun?
- Of course, sir, Major!
- You are given a finite automaton. You need to check whether it is a suffix machine gun for the given string.
Unfortunately, writing programs of this kind was not among the duties of Guido and Nunzio, either in the Syndicate or in the M.I.F. corporation. Therefore, you will have to write the appropriate program.
The input file contains one or more test sets. The first line of each set specifies the number of states of the automaton , the number of transitions , and the number of accepting states (1 \leq T \leq N \leq 50000, 1 \leq M \leq 100000). The second line contains different numbers in the range from to , separated by spaces, which are the accepting states of the automaton in ascending order. The next lines specify the transitions in the form a_i\ b_i\ c_i, where 1 \leq a_i, b_i \leq N, and c_i is a lowercase Latin letter. The transition occurs from state a_i to state b_i by letter c_i. From each state a_i, there is no more than one transition by symbol c_i. The last line of the set description is the string , for which the automaton must be a machine gun. It contains only lowercase Latin letters, and its length is from to inclusive. Moreover, the sum of all and the total length of all strings to be checked does not exceed , and the sum of all does not exceed .
The file ends with a dummy set for which N = M = T = 0.
The initial state of the automaton is the first one. If, while processing a string, the corresponding transition does not exist in the automaton, it fails and does not accept the string. Thus, a string is accepted only if all transitions during its interpretation exist, and after their completion the automaton is in an accepting state (whether there were accepting states along the way does not matter).
Print in the output file whether the given automaton is a machine gun, in the format given in the example.
Example 1