Substring Concatenation Finder

Given a string s and a list of words, each with the same length, find all starting indices in s where the substring is a concatenation of each word in the list exactly once and without any intervening characters. The words can be concatenated in any order.

Let \(L\) be the length of each word, and \(n\) be the number of words. Then the total length of the concatenated substring is \(n \times L\). Your task is to find all such starting indices in \(s\) where a window of length \(n \times L\) contains every word from the list exactly the same number of times as given.

Example: For s = "barfoothefoobarman" and words ["foo", "bar"], the answer is 0 9 because the substrings starting at indices 0 and 9 are "barfoo" and "foobar" respectively.

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains the string s.
The second line contains an integer n, representing the number of words.
Each of the next n lines contains a word.

Note: If n is 0, then there are no words.

outputFormat

Output a single line to standard output (stdout) containing the starting indices of the substrings that are concatenations of each word exactly once, separated by a space, in increasing order. If no such substring exists, output an empty line.

## sample

barfoothefoobarman
2
foo
bar

0 9

</p>