Word Scramble Puzzle

Given a scrambled string and a list of words, find and extract the words from the scrambled string in the order they appear in the list. For each word in the list, search for its occurrence within the scrambled string starting from the index immediately after the previous found word. If the word is found, include it in your output; otherwise, skip it. The search must be sequential and the words must be taken in order without rearranging any characters.

The algorithm should work as follows:

• Initialize a pointer at the beginning of the scrambled string.
• For each word in the list, search for it in the scrambled string starting at the current pointer.
• If found, append the word to the output list and move the pointer to the position just after the end of this word.
• If not found, move on to the next word in the list.

Mathematically, if we denote the scrambled string as S and the words as \(w_1, w_2, \ldots, w_n\), then for each valid i, find the smallest index \(p_i\) such that: \[ p_i = \min \{p \mid S[p:p+|w_i|] = w_i \text{ and } p \geq p_{i-1} + |w_{i-1}|\} \] with \(p_0 = 0\). If such \(p_i\) exists, include \(w_i\) in the output list.

If none of the words can be located in the correct sequence, return an empty output.

inputFormat

The input is read from standard input.

The first line contains the scrambled string S (a string without spaces).

The second line contains an integer n, representing the number of words.

The following n lines each contain a word from the list.

outputFormat

Print the found words in the order they appear in the word list. The words should be separated by a single space. If no words are found, print an empty line.

## sample

hellothisisateststring
3
hello
test
string

hello test string