Problem H. Hereditary string ≡

Statement

Vasya got a text string S as an inheritance from his grandmother. Vasya decided to play with this string.

On each step, Vasya picks a symbol and replaces every occurrence of this symbol with a space. Conversely, if this symbol is already replaced by space, Vasya replaces each of corresponding spaces back with the original symbol in the same position.

Your program must, after each step, determine the number of words (substrings of consequential non-spaces) currently present in the string.

Input format

First line of input contains string S. Following line contains string T, representing a sequence of symbols chosen by Vasya.

Strings consist of digits, small and capital Latin letters.

Output format

Output must contain a sequence of integers N_i — number of words in string S after step i.

Constraints

Symbol case does matter, i.e. small and capital letters are considered different.

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

Sample tests

1a2b3c4d1a2b3c4d
1234abcd

2
4
6
8
6
4
2
0

ababbcc11a2AAcc3
abca1234

3
2
3
4
4
5
4
4

Explanation

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

Выполним подсчет всех возможных цепочек из трех подряд идущих символов.
Для этого заведем вспомогательный массив C размером |A|³, где A — исходный алфавит.
Решение указанной задачи потребует от нас O(|S| + |A|³).

Так как по условию исходная строка S не имеет ни одного пробела, начальное число слов будем считать равным единице.

Заведем вспомогательный массив H, в котором каждому символу алфавита будем ставить в соответствие его состояние: (1 — видим, 0 — невидим).

Для каждого считанного символа T_i, выполняем перебор всех пар символов (α и β), с которыми он соседствует в строке S.

Если состояние обоих его соседей равно 1, и при этом сам символ также является видимым, то при его исключении между ними возникнет разрыв.
Тогда количество слов увеличится на общее число таких разрывов: C[α][T_i][β].
И наоборот, уменьшится, если символ T_i был до этого невидим.

Аналогичная ситуация возникает, когда состояния обоих соседей равны 0.
Число слов либо уменьшается, при удалении символа T_i,
либо увеличивается, при его добавлении.

Таким образом, общее время работы
второго этапа алгоритма составит O(|T| ⋅ |A|²).