Substring with Concatenated Words

You are given a string s and a list of words where all words have the same length. Your task is to find all starting indices of substrings in s that are a concatenation of each word in the list exactly once and without any intervening characters.

For example, given s = "barfoothefoobarman" and words = ["foo", "bar"], the output is [0, 9] because the substrings starting at indices 0 and 9 form "barfoo" and "foobar" respectively.

Note: Each word's length is denoted as \(L\) and the total number of words is \(n\). Thus, every valid substring in s must have a total length of \(n \times L\). If no concatenation exists, output an empty result.

inputFormat

The input is read from stdin and has the following format:

<s>
<n>
<word1 word2 ... wordn>

Here, the first line is the string s. The second line is an integer n representing the number of words. The third line contains n words separated by spaces.

outputFormat

Print a single line to stdout containing the starting indices of all the valid substrings in s separated by a single space. If there is no valid substring, output an empty line.

barfoothefoobarman
2
foo bar

0 9