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;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define show(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define show(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<62;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}


//base=9973,mod=999999937LL, 1000000007LL;
struct rolling_hash{
    int mnum;
	std::string str;
    long long int base;
	std::vector<long long int> mod;
    std::vector<vector<long long int>> hash,pow;

	rolling_hash(const std::string &str,long long int base,vector<long long int> mod):mnum(mod.size()),str(str),base(base),mod(mod){
		int size=str.size();
		hash=std::vector<std::vector<long long int>>(mnum,std::vector<long long int>(size+1));
		pow=std::vector<std::vector<long long int>>(mnum,std::vector<long long int>(size+1));

		for(int i=0; i<mnum; ++i){
            hash[i][0]=0;
            pow[i][0]=1;
        }
        for(int i=0; i<mnum; ++i){
            long long int m=mod[i];
    		for(int j=1; j<size+1; ++j){
    			pow[i][j]=pow[i][j-1]*base%m;
    			hash[i][j]=(hash[i][j-1]*base+str[j-1])%m;
    		}
        }
	}

	long long int compute_hash(int l,int r,int i){ //[l,r)
		return (hash[i][r]-hash[i][l]*pow[i][r-l]%mod[i]+mod[i])%mod[i];
	}

    bool match(int l,int r,const std::vector<long long int> &hs){
        for(int i=0; i<mnum; ++i) if(compute_hash(l,r,mod[i])!=hs[i]) return false;
        return true;
    }
};

void solve(){
    int n,m;
    string s;
    cin >> n >> m >> s;

    rolling_hash roriha(s,9973,{999999937LL, 1000000007LL});
    vector<pair<ll,ll>> v;
    int l=0,r=1;
    rep(i,0,m){
        string q;
        cin >> q;
        if(q=="R++") ++r;
        if(q=="R--") --r;
        if(q=="L++") ++l;
        if(q=="L--") --l;
        v.push_back(make_pair(roriha.compute_hash(l,r,0),roriha.compute_hash(l,r,1)));
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    cout << v.size() << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}