Задача H. Hereditary string ≡

Условие

Васе по наследству от бабушки досталась текстовая строка S. Вася решил поиграть с этой строкой.

На каждом шаге Вася выбирает символ и заменяет каждое вхождение этого символа на пробел. Если же выбранный символ уже заменён на пробел, то Вася, наоборот, заменяет каждый из соответствующих пробелов обратно на исходный символ в той же позиции.

Ваша программа должна после каждого шага определять, сколько слов (подстрок из подряд идущих не-пробелов) получилось в строке.

Формат входных данных

В первой строке входных данных содержится строка S. Далее следует строка T, задающая последовательность символов, выбираемых Васей.

Строки состоят из цифр, заглавных и строчных букв латинского алфавита.

Формат выходных данных

Выходные данные должны содержать последовательность целых чисел N_i — число слов в строке S после i-го шага.

Ограничения

Регистр символов имеет значение, т.е. заглавные и строчные буквы различны между собой.

1 ≤ |S| ≤ 10⁷, 1 ≤ |T| ≤ 10⁴

Примеры тестов

1a2b3c4d1a2b3c4d
1234abcd

2
4
6
8
6
4
2
0

ababbcc11a2AAcc3
abca1234

3
2
3
4
4
5
4
4