Substring

Time limit2sMemory limit512 MB

Summary

A window [l, r] over a string moves by changing one endpoint at a time, and after each of m queries you must count how many distinct substring values have appeared across all windows visited.

Level: Hard8 of 10
Topics: String, Sorting, String matching, Implementation
Solved: No attempts yet

Problem

You are given a string $s = s_1, s_2, \ldots, s_n$ of length $n$ and $m$ queries. Each query $q_k$ ( $1 \le k \le m$ ) is one of "L++", "L--", "R++", "R--". For the $k$ -th query $q_k$ , define $l[k]$ and $r[k]$ as follows.

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$

Here $l[0] = r[0] = 1$ .

Find the number of distinct strings among the $m$ substrings $s_{l[k]}, s_{l[k]+1}, \ldots, s_{r[k]-1}, s_{r[k]}$ ( $1 \le k \le m$ ).

Input

The input is given in the following format.

n m
s
q1
q2
…
qm

Output

Output the answer on one line.

Constraints

The string $s$ consists of lowercase English letters.
$1 \le n \le 3 \times 10^5$
$1 \le m \le 3 \times 10^5$
$q_k$ ( $1 \le k \le m$ ) is one of "L++", "L--", "R++", "R--".
$1 \le l[k] \le r[k] \le n$ ( $1 \le k \le m$ )

Examples3

Example 1
Input
```
5 4
abcde
R++
R++
L++
L--
```
Expected output
```
3
```
Example 2
Input
```
4 6
abab
R++
L++
R++
L++
R++
L++
```
Expected output
```
4
```

Example 3

Input

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

Expected output