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