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

Обмеження: 2 сек., 256 МіБ

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

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

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

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

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

Вхідні дані

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

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

Вихідні дані

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

Обмеження

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
abacaba ab	7

Примітки

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

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

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