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

Обмеження: 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\).