C - Snuke the Wizard Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 1

3 4
ABC
A L
B L
B R
A R

出力例 1

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

入力例 2

8 3
AABCBDBA
A L
B R
A R

出力例 2

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

入力例 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

Score : 500 points

Problem Statement

There are N squares numbered 1 to N from left to right. Each square has a character written on it, and Square i has a letter s_i. Besides, there is initially one golem on each square.

Snuke cast Q spells to move the golems.

The i-th spell consisted of two characters t_i and d_i, where d_i is L or R. When Snuke cast this spell, for each square with the character t_i, all golems on that square moved to the square adjacent to the left if d_i is L, and moved to the square adjacent to the right if d_i is R.

However, when a golem tried to move left from Square 1 or move right from Square N, it disappeared.

Find the number of golems remaining after Snuke cast the Q spells.

Constraints

  • 1 \leq N,Q \leq 2 \times 10^{5}
  • |s| = N
  • s_i and t_i are uppercase English letters.
  • d_i is L or R.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 4
ABC
A L
B L
B R
A R

Sample Output 1

2
  • Initially, there is one golem on each square.
  • In the first spell, the golem on Square 1 tries to move left and disappears.
  • In the second spell, the golem on Square 2 moves left.
  • In the third spell, no golem moves.
  • In the fourth spell, the golem on Square 1 moves right.
  • After the four spells are cast, there is one golem on Square 2 and one golem on Square 3, for a total of two golems remaining.

Sample Input 2

8 3
AABCBDBA
A L
B R
A R

Sample Output 2

5
  • After the three spells are cast, there is one golem on Square 2, two golems on Square 4 and two golems on Square 6, for a total of five golems remaining.
  • Note that a single spell may move multiple golems.

Sample Input 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

Sample Output 3

3