Зеник і рядки

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