Burdockvirus DNA

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

DNA (both of the burdockvirus, a human, and any other creature) can be represented as a string consisting of lowercase Latin letters.

As a result of long-term experiments, Zenik and Marichka built a theory of the effect of the burdockvirus on humans.

The similarity coefficient of two DNA sequences of the same length is defined as the sum of the indices (1-indexed) at which these sequences match.

The impact coefficient of a virus with DNA \(s\) on a human with DNA \(t\) is the sum of the similarity coefficients between \(s\) and all substrings of \(t\) of the same length as \(s\).

Write a program to find the impact coefficient of the virus on the human.

Input

The first line contains \(t\).

The second line contains \(s\).

Output

Print a single integer in one line — the impact coefficient of the virus with DNA \(s\) on the human with DNA \(t\).

Constraints

\(1 \le |t|, |s| \le 10^5\), where \(|x|\) is the length of the string \(x\),

\(s\) and \(t\) consist of lowercase Latin letters.

Samples

Input (stdin) сopy	Output (stdout) сopy
abacaba ab	7

Notes

Substrings of \(t\) of length 2: ab, ba, ac, ca, ab, ba.

Their similarity coefficients with \(s\): 3, 0, 1, 0, 3, 0.

\(3+0+1+0+3+0=7\).