Treasure Hunt#216
Once upon a time, an explorer found an ancient manuscript containing a map to a cave where the treasures of a distant ancient civilization were kept. It is known that this ancient civilization was highly intelligent, so the entrance to the cave was protected by a password. The manuscript included information on how to obtain this password. The ancient people used magical spells to summon evil spirits. On the cave door were many dots connected by arrows, each arrow labeled with a lowercase letter of the Latin alphabet.
According to ancient prophecy, the password can be obtained by following arrows from a specific (magical) starting dot to some other dot. Furthermore, the explorer discovered that the password appears as a substring in the magical spell for summoning evil spirits exactly times. Help the explorer find the password and reveal the treasures to the world. If there are several passwords that satisfy the conditions, any of them is acceptable. Also note that the manuscript may have been planted by enemies—in this case, there is no suitable password.
The first line contains the spell, a string of length (L \leq 10^5). The second line contains two numbers and (N, M \leq 10^5) — the number of dots and arrows. In the next lines, each arrow is described by the start dot, end dot, and a lowercase Latin letter. The last line contains the number (1 \leq k \leq L). By analyzing the drawing on the cave door, the explorer noticed that the number of different paths from the magical dot to the others does not exceed 10^5. All transitions are deterministic: from each dot, for each symbol, there is at most one transition.
The initial magical dot is numbered . All dots are numbered starting from one.
If there are suitable passwords, output all of them in lexicographical order, under the following conditions:
• Each password appears on a separate line;
• You cannot output a password if there is already another password in the list for which is a prefix.
If there are no suitable passwords, output an empty line. It is guaranteed that the length of the output file does not exceed characters.
Example 1