题目描述

左から右に向かって $1$ から $N$ の番号がついた $N$ 個のマスがあります。 各マスには文字が書かれており、マス $i$ には文字 $s_i$ が書かれています。また、各マスにははじめ $1$ 体のゴーレムがいます。

すぬけ君は $Q$ 回呪文を唱え、ゴーレムたちを移動させました。

$i$ 番目の呪文は文字 $t_i$ と $d_i$ からなり、$d_i$ は L か R のいずれかです。 すぬけ君がこの呪文を唱えると、$t_i$ が書かれた全てのマスについて、そのマスにいる全てのゴーレムが隣接するマスに移動します。移動する方向は $d_i$ が L ならば左、R ならば右です。

ただし、マス $1$ から左に移動しようとしたゴーレムと、マス $N$ から右に移動しようとしたゴーレムは消滅します。

$Q$ 回の呪文詠唱後に消滅していないゴーレムの総数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $s$ $t_1$ $d_1$ $\vdots$ $t_{Q}$ $d_Q$

输出格式

答えを出力せよ。

题目大意

从左到右有 $N$ 个从 $1$ 到 $N$ 的正方形，每个正方形上都有一个字符，第 $i$ 个正方形上有一个字母 $s_i$。此外，每个正方形上最初都有一个魔像。

斯努克施放 $Q$ 个法术移动魔像。

第 $i$ 个咒语由两个字符 $t_i$ 和 $d_i$ 组成，其中 $d_i$ 是 L 或 R.当 Snuke 施放此咒语时，对于每个具有字符 $t_i$ 的方块，如果 $d_i$ 为 L，并且如果 $d_i$ 为 R，则移至右侧附近的正方形。

但是，当魔像试图从第 1 个方块左移或从第 N 个方块右移时，它消失了。

找到施努克施放 $Q$ 咒语后剩余的魔像数量

3 4
ABC
A L
B L
B R
A R

2

8 3
AABCBDBA
A L
B R
A R

5

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

提示

制約

• $1\ \leq\ N,Q\ \leq\ 2\ \times\ 10^{5}$
• $|s|\ =\ N$
• $s_i,t_i$ は英大文字
• $d_i$ は L または R

Sample Explanation 1

- はじめ、各マスに $1$ 体のゴーレムがいます。 - $1$ 番目の呪文では、マス $1$ にいるゴーレムが左に移動しようとし、消滅します。 - $2$ 番目の呪文では、マス $2$ にいるゴーレムが左に移動します。 - $3$ 番目の呪文では、移動するゴーレムはいません。 - $4$ 番目の呪文では、マス $1$ にいるゴーレムが右に移動します。 - $4$ 回の呪文詠唱後、マス $2$ に $1$ 体、マス $3$ に $1$ 体のゴーレムがいるため、消滅していないゴーレムは $2$ 体です。

Sample Explanation 2

- $3$ 回の呪文詠唱後、マス $2$ に $1$ 体、マス $4$ に $2$ 体、マス $6$ に $2$ 体のゴーレムがいるため、消滅していないゴーレムは $5$ 体です。 - $1$ つの呪文で複数のゴーレムが移動しうることに注意してください。