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

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\).