У Dreamoon есть строка s и шаблон p. Сперва он удаляет ровно x символов из s, в результате чего получается строка s'. Затем он подсчитывает 
, которое определяется как максимальное количество непересекающихся подстрок, равняющихся p, которые можно выделить в s'. Он хочет, чтобы это число было как можно больше.
Более формально, определим 
как максимальное значение по всем s', которые можно получить, удалив ровно x символов из s.
Dreamoon хочет знать для всех x от 0 до |s|, где |s| обозначает длину строки s.
Выходные данные
Выведите на единственной строке |s| + 1 целых чисел через пробел — для всех x от 0 до |s|.
Примечание
В первом примере соответствующие оптимальные s' после удаления от 0 до |s| = 5 символов из s таковы: {«aaaaa», «aaaa», «aaa», «aa», «a», «»}.
Для второго примера оптимальные s' могут выглядеть как {«axbaxxb», «abaxxb», «axbab», «abab», «aba», «ab», «a», «»}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aaaaa
aa
|
2 2 1 1 0 0
|
|
2
|
axbaxxb
ab
|
0 1 1 2 1 1 0 0
|