分数: 500 点
问题陈述
有 N 编号的方块 1 to N 从左到右。 每个方格上都写有一个字符,而方格 i 有一封信 s_i。此外,最初每个方格上都有一个傀儡。
潜伏演员 Q 移动傀儡的法术。
的 i-第一个咒语由两个字符组成 t_i 和 d_i,其中 d_i is L or R。
当 Snuke 施展此法术时,对于角色所在的每个方格 t_i,如果满足以下条件,该方格上的所有傀儡都会移动到左侧相邻的方格 d_i is L,并移动到右侧相邻的方块,如果 d_i is R.
然而,当傀儡试图从广场向左移动时 1 或从 Square 向右移动 N,它消失了。
找出 Snuke 施放后剩余的傀儡数量 Q 咒语。
约束
- 1 \leq N,Q \leq 2 \times 10^{5}
- |s| = N
- s_i 和 t_i 为大写英文字母。
- d_i is
LorR.
输入
输入由标准输入按以下格式给出:
N Q
s
t_1 d_1
\vdots
t_{Q} d_Q
输出
打印答案。
示例输入 1
3 4 ABC A L B L B R A R
示例输出 1
2
- 最初,每个方格上都有一个傀儡。
- 在第一个咒语中,广场上的傀儡 1 尝试向左移动并消失。
- 在第二个咒语中,广场上的傀儡 2 向左移动。
- 在第三个咒语中,魔像没有移动。
- 在第四个咒语中,广场上的傀儡 1 向右移动。
- 施放四个法术后,广场上出现一个傀儡 2 和广场上的一个傀儡 3,总共剩下两个傀儡。
示例输入 2
8 3 AABCBDBA A L B R A R
示例输出 2
5
- 施展三个法术后,广场上出现一个傀儡 2,广场上的两个傀儡 4 和广场上的两个傀儡 6,总共剩下五个傀儡。
- 请注意,单个法术可以移动多个傀儡。
示例输入 3
10 15 SNCZWRCEWB B R R R E R W R Z L S R Q L W L B R C L A L N L E R Z L S L
示例输出 3
3