“Blake Technologies”公司的每位员工都使用特殊的消息应用程序“Blake Messenger”。所有的人都喜欢这个应用程序并不断使用它。然而,一些重要的未来却缺失了。例如,许多用户希望能够搜索消息历史记录。已经宣布新功能将出现在最近的更新中,当开发人员遇到一些只有你可以帮助他们解决的麻烦时。
所有消息均表示为仅由小写英文字母组成的字符串。为了减少网络负载,字符串以特殊的压缩形式表示。压缩算法的工作原理如下:字符串表示为 n 个块的串联,每个块仅包含相同的字符。一个块可以描述为一对(li,ci),其中li是第i个块的长度,ci是对应的字母。因此,字符串 s 可以写成 $${ \bigg < } ( l _ { 1 }, c _ { 1 } ), ( l _ { 2 }, c _ { 2 } ), \ldots, ( l _ { n }, c _ { n } ) { \bigg > }$$ 的序列对。
你的任务是编写程序,给定两个压缩字符串 t 和 s,找到 t 中所有出现的 s。开发人员知道这样的情况可能很多,所以他们只要求你找出其中的数量。请注意,p 是 t 中某些 s 出现的起始位置当且仅当 tptp + 1...tp + |s| - 1 = s,其中 ti 是字符串 t 的第 i 个字符。
请注意,以压缩形式表示字符串的方式可能不是唯一的。例如,字符串“aaaa”可以指定为 $$(4,a)$$, $${ \langle ( 3, a ), ( 1, a ) \rangle }$$, $${ \bigl \langle } ( 2, a ), ( 2, a ) { \bigr \rangle }$$...
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 200 000)——分别是字符串 t 和 s 中的块数。
第二行包含字符串 t 的 n 个部分的描述,格式为“li-ci”(1 ≤ li ≤ 1 000 000)——第 i 部分的长度和对应的小写英文字母。
第二行包含字符串 s 的 m 个部分的描述,格式为“li-ci”(1 ≤ li ≤ 1 000 000)——第 i 部分的长度和对应的小写英文字母。
输出
打印单个整数 — s 在 t 中出现的次数。
示例
输入 #1
5 3 3-a 2-b 4-c 3-a 2-c 2-a 2-b 1-c
输出 #1
1
输入 #2
6 1 3-a 6-b 7-a 4-c 8-e 2-a 3-a
输出 #2
6
输入 #3
5 5 1-h 1-e 1-l 1-l 1-o 1-w 1-o 1-r 1-l 1-d
输出 #3
0
注意
在第一个示例中,t =“aaabbccccaaacc”,字符串 s =“aabbc”。字符串 s 在字符串 t 中唯一出现的位置是从位置 p = 2 开始的。
在第二个示例中,t =“aaabbbbbbaaaaaaacccceeeeeeeeaa”,s =“aaa”。 t 中 s 的出现位置从 p = 1、p = 10、p = 11、p = 12、p = 13 和 p = 14 开始。