Problem: Given a string of length n s = s1, s2,…, sn and m queries. Each query qk (1 ≤ k ≤ m) is one of four types, "L ++", "L-", "R ++", "R-", and l [for the kth query qk. k] and r [k] are defined below.

* 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




However, l [0] = r [0] = 1.

At this time, how many kinds of character strings are created for m substrings sl [k], sl [k] + 1,…, sr [k] -1, sr [k] (1 ≤ k ≤ m). Answer if you can.

Constraints

* The string s consists of a lowercase alphabet

* 1 ≤ n ≤ 3 x 105

* 1 ≤ m ≤ 3 × 105

* qk (1 ≤ k ≤ m) is one of "L ++", "L-", "R ++", "R-"

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

Input

Input is given in the following format

> n m
> s
> q1
> q2
>…
> qm
>

Output

Output the solution of the problem on one line

Examples

Input

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


Output

3


Input

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


Output

4


Input

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


Output

11

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
 
using namespace std;

struct XorShift
{
    using result_type = uint32_t;
    result_type w = 123456789, x = 362436069, y = 521288629, z = 88675123;
    XorShift(result_type seed = time(nullptr))
    {
        w = seed;
        x = w << 13;
        y = (w >> 9) ^ (x << 6);
        z = y >> 7;
    }
    static const result_type min() { return 0; }
    static const result_type max() { return 0x7FFFFFFF; }
    result_type operator()()
    {
        result_type t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19) ^ (t ^ (t >> 8)));
    }
    result_type rand()
    {
        result_type t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19) ^ (t ^ (t >> 8)));
    }
    // [min,max] の整数値乱数
    result_type randInt(result_type min = 0, result_type max = 0x7FFFFFFF)
    {
        return rand() % (max - min + 1) + min;
    }
    // [min,max] の浮動小数点乱数
    double randDouble(double min = 0, double max = 1)
    {
        return (double)(rand() % 0xFFFF) / 0xFFFF * (max - min) + min;
    }
    // 変数をデフォルト値に設定する
    void SetDefault()
    {
        w = 123456789;
        x = 362436069;
        y = 521288629;
        z = 88675123;
    }
};
 
class RollingHash
{
    int n;
    XorShift rnd;
    static const uint64_t moda = (uint64_t)1e9 + 7;
    static const uint64_t modb = (uint64_t)1e9 + 9;
    // static const uint64_t b1 = (uint64_t)17, b2 = (uint64_t)19;
    uint64_t b1 = (uint64_t)rnd.randInt(2, 114514), b2 = (uint64_t)rnd.randInt(2, 114514);
    std::vector<uint64_t> a, b, p, q;

public:
    RollingHash(const std::string &str) : n((int)str.size()), a(n + 1, 0), b(n + 1, 0), p(n + 1, 1), q(n + 1, 1)
    {
        for (int i = 0; i < n; i++)
        {
            a[i + 1] = (a[i] * b1 + uint64_t(str[i])) % moda;
            b[i + 1] = (b[i] * b2 + uint64_t(str[i])) % modb;
            p[i + 1] = p[i] * b1 % moda;
            q[i + 1] = q[i] * b2 % modb;
        }
    }
    // [l, r) のハッシュ値を取得
    std::pair<uint64_t, uint64_t> query(int l, int r)
    {
        assert(0 <= l && l <= r && r <= n);
        uint64_t h1 = (p[r - l] * a[l] - a[r] + moda) % moda;
        uint64_t h2 = (q[r - l] * b[l] - b[r] + modb) % modb;
        return std::make_pair(h1, h2);
    }
};
 
using u64 = uint64_t;
using P = pair<u64, u64>;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    RollingHash rh(s);
    set<P> st;
    int l = 0, r = 1;
    for (int i = 0; i < m; i++)
    {
        string q;
        cin >> q;
        if (q == "L++")
        {
            l++;
        }
        else if (q == "L--")
        {
            l--;
        }
        else if (q == "R++")
        {
            r++;
        }
        else
        {
            r--;
        }
        st.insert(rh.query(l, r));
    }
    cout << st.size() << endl;
}