22481번 - Substring 다국어

長さnの文字列s=s₁,s₂,…,s_nおよびm個のクエリが与えられる。 各クエリq_k (1 ≤ k ≤ m)は、"L++", "L--", "R++", "R--"の4種類のいずれかであり、 k番目のクエリq_kに対して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個の部分文字列 s_l[k], s_l[k]+1, …, s_r[k]-1, s_r[k] (1 ≤ k ≤ m) について、何種類の文字列が作られるかを答えよ。

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

n m
s
q1
q2
…
qm

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

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

• 1 ≤ n ≤ 3×10⁵

• 1 ≤ m ≤ 3×10⁵

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

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