Hide

Problem C
Sliding

Languages en is

You have been sent some data from the genetics department of the university. They ask you to find where in the genetic code of their mutated flies a particular mutation can be found. Since these flies are quite heftily genetically altered, their DNA has 26 possible acids rather than 4 and thus the genetic code is given by a string consisting of lower case English letters. The mutation that should be found is also given as a string of lower case English letters. We say that the mutation $S$ appears in the genetic code $T$ at location $i$ if the letters $i, i + 1, \dots , i + |S| - 1$ in $T$ contain the same letters as $S$, though possibly in a different order than in $S$. $|S|$ denotes the length of $S$.

Input

The first line of the input contains the genetic data $S$ from the flies and the second line contains the mutation $T$ that should be searched after. The string $S$ is longer than the string $T$ and the length of $S$ does not exceed $10^5$ characters.

Output

Print all locations in $S$ where the mutation $T$ occurs.

Sample Input 1 Sample Output 1
abccba
bac
1
4