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