Substring Concatenation Indices

You are given a string s and a list of words. Your task is to find all starting indices in s where a concatenation of each word in the list exactly once and without any intervening characters appears. The words can appear in any order.

Let \( n \) be the number of words, and let \( l \) be the length of each word (all words are of equal length). The total length of the concatenated substring is \( n \times l \). Your job is to look for all substrings of this length which are a permutation of the list of words.

Example 1:

Input: s = "barfoothefoobarman", words = ["foo", "bar"]
Output: [0, 9]

Example 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"]
Output: []

Example 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]
Output: [6, 9, 12]

inputFormat

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

<string s>
<integer n>
<word 1>
<word 2>
...
<word n>

Where:

• s is the main string.
• n is the number of words in the list.
• Each of the following n lines contains one word.

outputFormat

Output to standard output (stdout) a single line with the starting indices separated by a single space. If there are no valid starting indices, output an empty line.

## sample

barfoothefoobarman
2
foo
bar

0 9