题目背景

至冬冬契军司令部，薇斯纳坐在桌前，面前的卷宗堆得像小山一样高。她翻了几页，忽然合上文件夹，抬头看向窗外的雪原。

“加密通讯里那些信号片段，交接点总是对不上。”她站起来，拿起桌上的军乐指挥杖在手里转了一圈，“冬契军的通讯协议，每一条指令结束的位置，必须是下一条指令开始的位置——但发给我的记录里，总有一段对不上。”

达妮卡站在门口：“您打算自己查？”

“不然呢？”薇斯纳把指挥杖往肩上一搁，迈步往外走，“让那些通信兵再报一遍？我亲自去通讯室看一眼就知道了。”

她走到门口，又回过头，补了一句：“对了，我桌上那叠卷宗，帮我重新整理一下——按指令类型分开放。达妮卡，你知道我说的是哪两种。”

达妮卡看着她消失在走廊尽头，叹了口气，走向那堆卷宗。

雪还在下，司令部里的灯光在风雪中显得格外安静。

题目描述

给定一个长度为 $n$ 的字符串 $s$。给定两类片段：$A$ 类和 $B$ 类。

求有多少对 $(i,a,b)$，使得 $A$ 类第 $a$ 个片段在 $i$ 处结束，且 $B$ 类第 $b$ 个片段在 $i+1$ 处开始。

输出这个总数。

输入格式

从文件 cipher.in 中读入数据。

第一行一个整数 $n$，表示字符串长度。

第二行一个长度为 $n$ 的字符串 $s$（仅包含小写字母）。

第三行两个整数 $A, B$，分别表示 $A$ 类片段和 $B$ 类片段的数量。

接下来 $A$ 行，每行一个字符串，表示 $A$ 类片段。

接下来 $B$ 行，每行一个字符串，表示 $B$ 类片段。

允许不同编号的片段内容相同。

输出格式

输出到文件 cipher.out 中。

输出一行一个整数，表示满足条件的组合总数。

注意答案可能超过 $32$ 位整数的存储范围。

样例 1 输入

12
abababababab
2 1
aba
bab
ab

样例 1 输出

4

样例 1 解释

共有 4 个匹配：$(4,2,1),\ (6,2,1),\ (8,2,1),\ (10,2,1)$。

样例 2 输入

6
aaaaaa
2 1
aa
aaa
a

样例 2 输出

7

样例 3

见选手目录下的 cipher/cipher3.in 与 cipher/cipher3.ans。

样例 4

见选手目录下的 cipher/cipher4.in 与 cipher/cipher4.ans。

数据范围

对于所有测试数据，保证：$1 \le n \le 5 \times 10^6 , 1 \le 片段总长 \le 2 \times 10^6, 1 \le A,B \le 2 \times 10^5$，允许不同编号的片段内容相同。

特殊性质 $A$ : 所有编号的片段均不相同。