配点 : $500$ 点

問題文

左から右に向かって $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$ 回の呪文詠唱後に消滅していないゴーレムの総数を求めてください。

制約

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

入力

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

$N$ $Q$

$s$

$t_1$ $d_1$

$\vdots$

$t_{Q}$ $d_Q$

出力

答えを出力せよ。

3 4
ABC
A L
B L
B R
A R

2

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

8 3
AABCBDBA
A L
B R
A R

5

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

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