Substring

時間制限 : 2 sec, メモリ制限 : 65536 KB

Substring

長さnの文字列s=s1,s2,…,snおよびm個のクエリが与えられる。 各クエリqk (1 ≤ k ≤ m)は、"L++", "L--", "R++", "R--"の4種類のいずれかであり、 k番目のクエリqkに対してl[k]とr[k]を以下で定義する。

  • L++:l[k]=l[k-1]+1,r[k]=r[k-1]

  • L--:l[k]=l[k-1]-1,r[k]=r[k-1]

  • R++:l[k]=l[k-1],r[k]=r[k-1]+1

  • R--:l[k]=l[k-1],r[k]=r[k-1]-1

但し、l[0]=r[0]=1である。

この時、m個の部分文字列 sl[k], sl[k]+1, …, sr[k]-1, sr[k] (1 ≤ k ≤ m) について、何種類の文字列が作られるかを答えよ。

Input

入力は以下の形式で与えられる

n m
s
q1
q2

qm

Constraints

  • 文字列sは小文字アルファベットからなる

  • 1 ≤ n ≤ 3×105

  • 1 ≤ m ≤ 3×105

  • qk(1 ≤ k ≤ m)は、"L++"、"L--"、"R++"、"R--"のいずれか

  • 1 ≤ l[k] ≤ r[k] ≤ n (1 ≤ k ≤ m)

Output

問題の解を1行に出力せよ

Sample Input 1

5 4
abcde
R++
R++
L++
L--

Output for the Sample Input 1

3
  • l[1]=1, r[1]=2であり、部分文字列は"ab"である

  • l[2]=1, r[2]=3であり、部分文字列は"abc"である

  • l[3]=2, r[3]=3であり、部分文字列は"bc"である

  • l[4]=1, r[4]=3であり、部分文字列は"abc"である

よって、生成される文字列は{"ab","abc","bc"}の3種類である。

Sample Input 2

4 6
abab
R++
L++
R++
L++
R++
L++

Output for the Sample Input 2

4
  • l[1]=1, r[1]=2であり、部分文字列は"ab"である

  • l[2]=2, r[2]=2であり、部分文字列は"b"である

  • l[3]=2, r[3]=3であり、部分文字列は"ba"である

  • l[4]=3, r[4]=3であり、部分文字列は"a"である

  • l[5]=3, r[5]=4であり、部分文字列は"ab"である

  • l[6]=4, r[6]=4であり、部分文字列は"b"である

よって、生成される文字列は{"a","ab","b","ba"}の4種類である。

Sample Input 3

10 13
aacacbabac
R++
R++
L++
R++
R++
L++
L++
R++
R++
L--
L--
R--
R--

Output for the Sample Input 3

11

Source: ACM-ICPC Japan Alumni Group Summer Camp , Day 3 B, Tokyo, Japan, 2012-09-16
http://acm-icpc.aitea.net/