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 int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define pb            push_back
#define mp            make_pair
template<class T, class S> inline bool minup(T& m, const S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, const S x){ return m<(T)x ? (m=(T)x, true) : false; }

const int    INF = 1000000000;
const ll     MOD = 1000000007LL;
const double EPS = 1E-10;

typedef long long int llu;
const llu MODD[3] = {1000000009, 2000000011, 3000000019};
const llu base[3] = {901502696, 617916109, 103244261};
const llu basi[3] = {938106584, 434659818, 480258097};
llu B = 100000007LLU;
llu BI = 158730160LLU;
int n, m;
string s;
string q[333333];
llu b[3][333333];

template<typename T> T modMulti(T x, T y, T mod = MOD)
{
  T res = 0;
  x %= mod;
  while(y > (T)0){
    if(y & (T)1) res = (res + x) % mod;
    x = (x << 1) % mod;
    y >>= 1;
  }
  return res;
}

int main(int argc, char *argv[])
{
  cin >> n >> m;
  cin >> s;
  rep(i, m) cin >> q[i];
  rep(i, 3) b[i][0] = 1LL;
  rep(i, 3) rep(j, m) b[i][j + 1] = b[i][j] * base[i] % MODD[i];

  llu H[3] = {s[0], s[0], s[0]};
  int l = 0;
  int r = 0;
  vector<vector<llu> > can;
  rep(i, m){
    rep(j, 3){
      if(q[i] == "L++") H[j] += - (b[j][r - l] * s[l]) % MODD[j];
      if(q[i] == "L--") H[j] += b[j][r - l + 1] * s[l - 1];
      if(q[i] == "R++") H[j] = modMulti(H[j], base[j], MODD[j]) + s[r + 1];
      if(q[i] == "R--") H[j] = modMulti(H[j] - s[r] + MODD[j], basi[j], MODD[j]);
      if(H[j] < 0) H[j] += MODD[j];
      H[j] %= MODD[j];
    }
    if(q[i] == "L++") l += 1;
    if(q[i] == "L--") l -= 1;
    if(q[i] == "R++") r += 1;
    if(q[i] == "R--") r -= 1;
    vector<llu> tmp;
    rep(j, 3) tmp.pb(H[j]);
    can.pb(tmp);
  }

  sort(ALL(can));
  can.erase(unique(ALL(can)), can.end());

  cout << can.size() << endl;
  
  return 0;
}