ДНК реп'яховірусу

Limits: 2 sec., 256 MiB

ДНК (і реп’яховірусу, і людини, і будь-якої іншої істоти) можна представити у вигляді рядка, що складається з маленьких літер латинської абетки.

У результаті довготривалих експериментів Зеник та Марічка побудували теорію впливу реп’яховірусу на людину.

Коефіцієнтом подібності двох послідовностей ДНК однакової довжини називається сума індексів (починаючи з одиниці), у яких ці послідовності збігаються.

Коефіцієнтом впливу вірусу з ДНК $s$ на людину з ДНК $t$ називається сума коефіцієнтів подібності між $s$ та всіма підрядками $t$ такої ж довжини, як $s$.

Напишіть програму для знаходження коефіцієнту впливу вірусу на людину.

Input

У першому рядку задано $t$.

У другому рядку задано $s$.

Output

В одному рядку виведіть ціле число — коефіцієнт впливу вірусу з ДНК $s$ на людину з ДНК $t$.

Constraints

$1 \le |t|, |s| \le 10^5$, де $|x|$ — це довжина рядка $x$,

$s$ і $t$ складаються з малих літер латинської абетки.

Samples

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

Notes

Підрядки $t$ довжини 2: ab, ba, ac, ca, ab, ba.

Їхні коефіцієнти подібності з $s$: 3, 0, 1, 0, 3, 0.

$3+0+1+0+3+0=7$.