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;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
//#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

unordered_set<ll>S[300005];
int n,m;
char f[300005];
ll b[300005][2];
ll r[300005][2];
ll rui[300005][2];
ll mod[2] = {1000000007, 1000000009};
ll inv[2] ;
ll modpow(ll x,ll n,ll mod){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%s",&f);
	b[0][0] = b[0][1] = r[0][0] = r[0][1] = 1;
	inv[0] = modpow(32LL,mod[0]-2,mod[0]);
	inv[1] = modpow(32LL,mod[1]-2,mod[1]);
	for(int i=1;i<=n;i++){
		rep(k,2){
			b[i][k] = b[i-1][k] * 32LL % mod[k];
			r[i][k] = r[i-1][k] * inv[k] % mod[k];
			rui[i][k] = rui[i-1][k] + b[i][k]*(f[i-1]-'a'+1);
			rui[i][k] %= mod[k];
		}
	}
	int L = 1, R = 1;
	rep(i,m){
		char f[6]; scanf("%s",&f);
		if(f[0] == 'L'){
			if(f[1] == '+') L++;
			else L--;
		}
		else{
			if(f[1] == '+') R++;
			else R--;
		}
		if(L > R){
			S[0].insert(0LL);
		}
		else{
			ll RR[2];
			rep(k,2){
				RR[k] = rui[R][k] - rui[L-1][k];
				RR[k] *= r[L-1][k];
				RR[k] %= mod[k];
				if(RR[k] < 0) RR[k] += mod[k];
			}
			S[R-L+1].insert(RR[0] * 1000000100LL + RR[1]);
		}
	}
	int ans = 0;
	rep(i,300005) ans += S[i].size();
	cout<<ans<<endl;
}