E. Вам задана строка...
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана строка $$$t$$$ и $$$n$$$ строк $$$s_1, s_2, \dots, s_n$$$. Все строки состоят из строчных букв латинского алфавита.

Пусть $$$f(t, s)$$$ равно количеству вхождений строки $$$s$$$ в строку $$$t$$$. Например, $$$f('\text{aaabacaa}', '\text{aa}') = 3$$$, и $$$f('\text{ababa}', '\text{aba}') = 2$$$.

Посчитайте значение $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$, где $$$s + t$$$ — конкатенация строк $$$s$$$ и $$$t$$$. Обратите внимание, что если есть две пары $$$i_1$$$, $$$j_1$$$ и $$$i_2$$$, $$$j_2$$$, такие что $$$s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}$$$, вы должны учесть и $$$f(t, s_{i_1} + s_{j_1})$$$, и $$$f(t, s_{i_2} + s_{j_2})$$$.

Входные данные

Первая строка содержит строку $$$t$$$ ($$$1 \le |t| \le 2 \cdot 10^5$$$).

Вторая строка содержит число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Каждая из следующих $$$n$$$ строк содержит строку $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^5$$$).

Гарантируется, что $$$\sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5$$$. Все строки состоят из строчных букв латинского алфавита.

Выходные данные

Выведите число — значение $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$.

Примеры
Входные данные
aaabacaa
2
a
aa
Выходные данные
5
Входные данные
aaabacaa
4
a
a
a
b
Выходные данные
33