Find Substring Concatenation Indices

You are given a string s and a list of words words where each word has the same length. Your task is to find all starting indices in s at which a substring is formed by the concatenation of each word in words exactly once and without any intervening characters.

Let the length of each word be denoted by \(L\) and the total number of words be \(n\). Then, the total length of the concatenated substring is \(n \times L\). For every index \(i\) in s, consider the substring \(s[i, i+n \times L)\). If this substring can be segmented into \(n\) pieces of length \(L\) each matching the words in words (including duplicates), then \(i\) is a valid starting index.

Note: If there is no valid index, the program should output an empty line.

inputFormat

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

1. A line containing the string s.
2. A line containing an integer n which represents the number of words.
3. n subsequent lines, each containing one word from the list words.

outputFormat

Output to standard output (stdout) the starting indices (separated by a single space) where the concatenation of all words in words appears in s. If there are no valid indices, output an empty line.

## sample

barfoothefoobarman
2
foo
bar

0 9

</p>