Зеник і рядки

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

У Зеника є набір \(n\) рядків \(s_i\) та рядок \(t\).

Йому стало цікаво, наскільки рядок \(t\) гармонійно поєднується з набором.

Зеник визначає гармонійність рядка \(t\) й набору \(s\) як \(\sum_{i = 1} ^{n} f(s_i, t)\), де \(f(s, t) = \sum_{i=1}^{|t|} |lcp(s, t_{i..|t|})|\), \(|t|\) — довжина рядка \(t\), \(t_{i..|t|}\) — суфікс рядка \(t\), що починається в позиції \(i\), \(lcp(s, t)\) — найдовший спільний префікс рядків \(s\) і \(t\).

Допоможіть Зенику порахувати гармонійність його рядків.

Вхідні дані

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

У другому рядку записано ціле число \(n\) — кількість рядків у наборі.

У наступних \(n\) рядках задано \(s_i\).

Вихідні дані

В одному рядку виведіть ціле число — відповідь на задачу.

Обмеження

\(1 \le |t| \le 10^5\),

\(1 \le n \le 10^5\),

\(1 \le \sum_{i=1} ^n |s_i| \le 10^5\),

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

Приклади