Substring Concatenation Indices

You are given a string S and a list of words L. Each word in L has the same length. Your task is to find all starting indices in S such that the substring starting at that index is equal to the concatenation of each word in L exactly once and without any intervening characters.

More formally, let each word have length \(w\) and let there be \(n\) words. You need to find all indices \(i\) such that the substring \(S[i:i+n\times w]\) can be partitioned into \(n\) contiguous substrings of length \(w\), which is a permutation of the list \(L\).

If no such substring exists, output -1.

inputFormat

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

1. A string S on the first line.
2. An integer n on the second line, representing the number of words in the list L.
3. A single line containing n words separated by spaces.

outputFormat

Output the starting indices as a sequence of integers separated by a space. If there is no valid concatenation, output a single -1.

barfoothefoobarman
2
foo bar

0 9