AT_exawizards2019_c Snuke the Wizard

[problemUrl]: https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_c 左から右に向かって $ 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 $

答えを出力せよ。

### 制約 - $ 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 $ つの呪文で複数のゴーレムが移動しうることに注意してください。