У Громозеки есть его любимая строка S и другая строка T. Он внимательно посмотрел на свои строки и понял, что первая строка (S) может содержать в себе несколько раз вторую строку (T). Громозека подсчитал все вхождения строки T в строку S и написал себе в порядке возрастания список индексов, начиная с которых строка T входит в строку S. Однако, путешествуя по Галактике, Громозека потерял этот список и пришел в уныние. Помогите Громозеке восстановить потерянный список.
Формат входных данных
Первые две строки входных данных содержат строки
S и
T, соответственно. Длины строк больше 0 и меньше 50000, строки содержат только строчные латинские буквы.
Формат выходных данных
Выведите в порядке возрастания индексы символов, начиная с которых строка
T входит в строку
S (в одной строке должно быть записано одно число).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
ababbababa
aba
|
0
5
7
|