Choosing the path of a politician and commander, Caesar had little time for creative work, but wrote compositions of various genres: the epic poem "Hercules", the tragedy "Oedipus Rex", the poem "Journey", " Notes on the Gallic War" and "Notes on the Civil War". Collections of his maxims, speeches, and letters were published. In addition, the great commander was interested in philology.
Taking a break from writing the poem, Caesar wrote down two lines one under the other and thought. Then he looked at the written lines and realized that the first line (S) could contain several times the second line (T). Gaius Julius Caesar decided to count all occurrences of the string T into the string S. Help him, write the appropriate program.
Input
The first two lines of the input contain the strings
S and
T, respectively. The string lengths are greater than 0 and less than 50000, the strings contain only lowercase Latin letters.
Imprint
Print the numbers of characters starting from which the string
T includes in the string
S, in ascending order (one value per line).
Examples
| # |
Input |
Output |
| 1 |
ababbababa
aba |
0
5
7 |