Treasure Hunt
Once upon a time, Losyash discovered an ancient manuscript containing a map that led to an old cave, where the treasures of the Smeshariki's distant ancestors were hidden. The ancient Smeshariki were known for their intellect, and thus, the cave's entrance was secured with a password. The manuscript provided instructions on how to determine this password. The ancient Smeshariki used a magical spell to summon evil spirits. On the cave door, there were numerous dots connected by arrows, each arrow labeled with a lowercase letter from the Latin alphabet. According to an ancient prophecy, the password could be found by tracing the arrows from a specific starting dot (magical) to another. Additionally, Losyash learned that the password appears as a substring in the magical spell exactly k times. Help Losyash uncover the password to reveal the treasures of the ancient Smeshariki to the world. If multiple passwords satisfy the conditions, any one of them will suffice. However, be aware that the manuscript might be a trap set by enemies, in which case the password does not exist.
Input
The first line contains the spell, with a length of L ≤ 10^5. The second line contains the numbers N and M (N, M ≤ 10^5)—representing the number of dots and arrows, respectively. The following M lines provide details about the arrows: the starting dot number, the ending dot number, and a lowercase letter of the Latin alphabet. The last line contains the number k (1 ≤ k ≤ L). Upon examining the cave door's illustration, Losyash noticed that the number of distinct paths from the magical dot to all others does not exceed 10^5. Fortunately, Losyash also found that all transitions are deterministic, meaning from each dot, there is at most one path for any given symbol.
The initial magical dot is numbered 1. All dots are numbered starting from one.
Output
If passwords exist, output all of them in lexicographical order, ensuring the following conditions are met:
• Each password is output on a separate line;
• You cannot output a password X if there is another password in the output list for which X is a prefix.
If no passwords exist, the output file should contain an empty line. It is guaranteed that the length of the output file does not exceed 120000 characters.