Зеник і рядки

Limits: 2 sec., 256 MiB

У Зеника є набір \(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\).

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

Input

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

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

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

Output

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

Constraints

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

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

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

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

Samples