Problem H. Hereditary string

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

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 Ni — 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| ≤ 107, 1 ≤ |T| ≤ 104

Sample tests

No. Standard input Standard output
1
1a2b3c4d1a2b3c4d
1234abcd
2
4
6
8
6
4
2
0
2
ababbcc11a2AAcc3
abca1234
3
2
3
4
4
5
4
4

0.072s 0.012s 13