Підрядки в словнику
Limits: 2 sec., 512 MiB
Зеник і Марічка мають набір із \(n\) рядків \(s_1, s_2, ... s_n\). Також у них є рядок \(t\).
Їх цікавить, скільки підрядків \(t[l..r]\) (\(1 \le l \le r \le |t|\)) містять хоча б одне входження довільного слова із набору \(s\). Допоможіть їм знайти цю кількість.
Input
У першому рядку вхідних даних задано одне ціле число \(n\) — кількість рядків у наборі \(s\).
У наступних \(n\) рядках задано непусті рядки \(s_i\), по одному на рядок.
У останньому рядку задано рядок \(t\).
Output
Виведіть одне ціле число — відповідь на задачу.
Constraints
\(1 \le n, |t| \le 3 \cdot 10^5\),
сумарна довжина рядків \(s_i\) не перевищує \(3 \cdot 10^5\),
усі рядки складаються лише із малих англійських букв.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 aa aba ca abcabaacbaccaa | 71 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|