Suffix machine gun
_Pass or Automatic.___________________
Hannibal Rector
The theoretical training for recruits in the Possiltum army included classes not only in military law but also in the basics of cryptography. These lectures were delivered by Major Mega Byte, known for his characteristic soldier's humor. Guido and Nunzio, tasked with dismantling the Possiltum army from within, decided to exploit this by creating confusion in the terminology. At the start of the next lecture, Nunzio raised his hand and asked:
- You mentioned finite automata in the previous lecture. Could you explain what finite machine guns are?
Mega Byte was unfazed.
- A suffix machine gun is a finite automaton that accepts all suffixes of a given string (from zero to L-th inclusive, where L is the length of the string), and only them. Sergeant Guido!
- Yes, Major!
- Can you tell the difference between an automaton and a machine gun?
- Yes, sir, Major!
- You have been given a finite automaton. Your task is to determine if it is a suffix machine gun for the given string.
Unfortunately, writing programs of this nature was not part of Guido and Nunzio's responsibilities, either in the Syndicate or in the M.I.F. corporation. Therefore, you will need to write the appropriate program.
Input
The input file contains one or more test sets. The first line of each set specifies the number of states of the automaton N, the number of transitions M, and the number of accepting states T (1 ≤ T ≤ N ≤ 50000, 1 ≤ M ≤ 100000). The second line contains T different numbers in the range from 1 to N - the accepting states of the automaton, in ascending order. The next M lines specify transitions in the form a_i b_i c_i, where 1 ≤ a_i, b_i ≤ 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 S, for which the automaton must be a machine gun. It consists only of lowercase Latin letters, and its length is between 1 and 50000 inclusive. Moreover, the sum of all N and the total length of all strings for which verification is required does not exceed 50000, and the sum of all M does not exceed 100000.
The file ends with a dummy set, where N=M=T=0.
The initial state of the automaton is the first one. If, when interpreting any string, there is no corresponding transition in the automaton, it fails with an error and does not accept the string. Thus, a string is accepted only if all transitions were found during its interpretation, and upon their completion, the automaton is in an accepting state (it does not matter if there were accepting states on the path or not).
Output
Output to the output file whether the given automaton is a machine gun, following the example format.