Migrated from Lutece 1575 Hesty Str1ng Again

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A Palindrome string is a string which reads the same backward as forward, such as $\texttt{madam}$ or $\texttt{racecar}$

There is a problem about the palindrome string again.

You are given a pattern string $S$ with the length $N$. For another string $T$, we can define its similarity with $S$ by

$$Sim(T, S) = |\{(i,~j)~|~1 \leq i \leq j \leq N~\mathrm{and}~(T~+~S_{i \dots j})~\mathrm{is~a~palindrome~string}\}|, $$

where "$S_{i \dots j}$'' denotes the substring of $S$ from the position $i$ to $j$ and "$+$'' means the string concatenate operation.

Now, for a given string $T$ with the length $M$, you need to calculate all its prefixes' similarity with $S$, i.e., calculate

$Sim(T_{1 \dots 1}, S), Sim(T_{1 \dots 2}, S), \dots, Sim(T_{1 \dots M}, S)$.

Input

The first line contains a string $T$.

The second line contains a sting $S$.

$1 \leq |T|, |S| \leq 10^5$, both $T$ and $S$ are composed by lowercase English characters.

Output

Print $|T|$ lines, for the $i_{th}$ line, print $Sim(T_{1 \dots i}, S)$.

Samples

aaba
aba

3
2
0
2

Resources

The 15th UESTC Programming Contest Final